Theories for TC0 and Other Small Complexity Classes

Details Theories for TC0 and Other Small Complexity Classes Theories for TC0 and Other Small Complexity Classes

2005-05-05

arxiv.org/abs/cs/0505013v4

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-693440