BIT predicate

In mathematical logic, the BIT predicate, sometimes written BIT(i,j), is a predicate which tests whether the "j"th 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. cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | id = ISBN 0-387-98600-6] . 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.cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | id = ISBN 0-387-98600-6 | pages = 14-16]

The BIT predicate is also examined in circuit complexity.

References