Set data structures For a set represented as a
bit array, the BIT predicate can be used to test set membership. For instance, subsets of the non-negative integers \{0, 1, \ldots\} may be represented by a bit array with a one in when i is a member of the subset, and a zero in that position when it is not a member. When such a bit array is interpreted as a binary number, the set \{i,j,k,\dots\} for distinct i,j,k,\dots is represented as the binary number 2^i+2^j+2^k+\cdots. If S is a set, represented in this way, and i is a number that may or may not be an element of S, then \text{BIT}(S,i) returns a nonzero value when i is a member and zero when it is not. The same technique may be used to test membership in subsets of any sequence x_0,x_1,\dots of distinct values, encoded using powers of two whose exponents are the positions of the elements in this sequence, rather than their values. For instance, in the
Java collections framework, java.util.EnumSet uses this technique to implement a set data structure for
enumerated types. Ackermann's encoding of the hereditarily finite sets is an example of this technique, for the recursively-generated sequence of hereditarily finite sets.
Private information retrieval In the mathematical study of
computer security, the
private information retrieval problem can be modeled as one in which a client, communicating with a collection of servers that store a binary wishes to determine the result of a BIT predicate \text{BIT}(i,j) without divulging the value to the servers. describe a method for replicating i across two servers in such a way that the client can solve the private information retrieval problem using a substantially smaller amount of communication than would be necessary to recover the complete value
Complexity and logic The BIT predicate is often examined in the context of
first-order logic, where systems of logic result from adding the BIT predicate to first-order logic. In
descriptive complexity, the
complexity class FO describes the class of
formal languages that can be described by a formula in first-order logic with a comparison operation on
totally ordered variables (interpreted as the indexes of characters in a
string) and with predicates that test whether this string has a given character at a given numerical index. A formula in this logic defines a language consisting of its
finite models. However, with these operations, only a very restricted class of languages, the
star-free regular languages, can be described. Adding the BIT predicate to the repertoire of operations used in these logical formulas results in a more robust complexity class, , meaning that it is less sensitive to minor variations in its definition. The class is the same as the class , of first-order logic with addition and multiplication predicates. It is also the same as the
circuit complexity class
DLOGTIME-
uniform AC0. Here, AC0 describes the problems that can be computed by circuits of
AND gates and
OR gates with polynomial size, bounded height, and unbounded fanout. "Uniform" means that the circuits of all problem sizes must be described by a single algorithm. More specifically, it must be possible to index the gates of each circuit by numbers in such a way that the type of each gate and the adjacency between any two gates can be computed by a
deterministic algorithm whose time is logarithmic in the size of the circuit (DLOGTIME).
Construction of the Rado graph In 1964, German–British mathematician
Richard Rado used the BIT predicate to construct the infinite
Rado graph. Rado's construction is just the
symmetrization of Ackermann's 1937 construction of the hereditary finite sets from the BIT predicate: two vertices numbered i and j are adjacent in the Rado graph when either \text{BIT}(i,j) or \text{BIT}(j,i) is nonzero. The resulting graph has many important properties: it contains every finite undirected graph as an
induced subgraph, and any
isomorphism of its induced subgraphs can be extended to a symmetry of the whole graph. ==Notes==