BIT predicate
In mathematics and computer science, the BIT predicate, sometimes written
Its mathematical applications include modeling the membership relation of hereditarily finite sets, and defining the adjacency relation of the Rado graph.
In computer science, it is used for efficient representations of set data structures using bit vectors, in defining the private information retrieval problem from communication complexity, and in descriptive complexity theory to formulate logical descriptions of complexity classes.
The BIT predicate was first introduced in 1937 by Wilhelm Ackermann to define the Ackermann coding, which encodes hereditarily finite sets as natural numbers.
[1][2] The BIT predicate can be used to perform membership tests for the encoded sets:
, and the name "the BIT predicate", come from the work of Ronald Fagin and Neil Immerman, who applied this predicate in computational complexity theory as a way to encode and decode information in the late 1980s and early 1990s.
It is commonly written in binary notation as just the sequence of these bits,
[6] The BIT predicate is a primitive recursive function.
[2][7] As a binary relation (producing true and false values rather than 1 and 0 respectively), the BIT predicate is asymmetric: there do not exist two numbers
[b] In programming languages such as C, C++, Java, or Python that provide a right shift operator >> and a bitwise Boolean and operator &, the BIT predicate
The subexpression i>>j shifts the bits in the binary representation of
For instance, subsets of the non-negative integers
When such a bit array is interpreted as a binary number, the set
[c] The same technique may be used to test membership in subsets of any sequence
For instance, in the Java collections framework, java.util.EnumSet uses this technique to implement a set data structure for enumerated types.
[11] Ackermann's encoding of the hereditarily finite sets is an example of this technique, for the recursively-generated sequence of hereditarily finite sets.
[d] 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 number
, wishes to determine the result of a BIT predicate
Chor et al. (1998) describe a method for replicating
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 of
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.
[15] Adding the BIT predicate to the repertoire of operations used in these logical formulas results in a more robust complexity class, FO[BIT], meaning that it is less sensitive to minor variations in its definition.
[f] The class FO[BIT] is the same as the class FO[+,×], of first-order logic with addition and multiplication predicates.
[14] 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).
Rado's construction is just the symmetrization of Ackermann's 1937 construction of the hereditary finite sets from the BIT predicate: two vertices numbered
[17] 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.
