Computer Science – Logic in Computer Science
Scientific paper
2005-05-05
LMCS 2 (1:3) 2006
Computer Science
Logic in Computer Science
40 pages, Logical Methods in Computer Science
Scientific paper
10.2168/LMCS-2(1:3)2006
We present a general method for introducing finitely axiomatizable "minimal" two-sorted theories for various subclasses of P (problems solvable in polynomial time). The two sorts are natural numbers and finite sets of natural numbers. The latter are essentially the finite binary strings, which provide a natural domain for defining the functions and sets in small complexity classes. We concentrate on the complexity class TC^0, whose problems are defined by uniform polynomial-size families of bounded-depth Boolean circuits with majority gates. We present an elegant theory VTC^0 in which the provably-total functions are those associated with TC^0, and then prove that VTC^0 is "isomorphic" to a different-looking single-sorted theory introduced by Johannsen and Pollet. The most technical part of the isomorphism proof is defining binary number multiplication in terms a bit-counting function, and showing how to formalize the proofs of its algebraic properties.
Cook Stephen
Nguyen Phuong
No associations
LandOfFree
Theories for TC0 and Other Small Complexity Classes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Theories for TC0 and Other Small Complexity Classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Theories for TC0 and Other Small Complexity Classes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-693440