BIT predicate

From Wikipedia, the free encyclopedia

In mathematical logic, the BIT predicate, sometimes written BIT(i,j), is a predicate which tests whether the jth bit of the number i is 1, when i is written in binary. The BIT predicate is often examined in the context of first-order logic, where we can examine the system resulting from adding the BIT predicate to first-order logic. In descriptive complexity, the complexity class FO+BIT resulting from adding the BIT predicate to FO results in a more robust complexity class. [1]. We can also prove that the class FO+BIT, of first-order logic with the BIT predicate, is the same as the class FO+PLUS+TIMES, of first-order logic with addition and multiplication predicates.[2]

The BIT predicate is also examined in circuit complexity.

[edit] References

  1. ^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6. 
  2. ^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag, 14-16. ISBN 0-387-98600-6.