Nguyen, Phuong and Cook, Stephen - Theories for TC0 and Other Small Complexity Classes

lmcs:2257 - Logical Methods in Computer Science, March 7, 2006, Volume 2, Issue 1
Theories for TC0 and Other Small Complexity Classes

Authors: Nguyen, Phuong and Cook, Stephen

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.


Source : oai:arXiv.org:cs/0505013
DOI : 10.2168/LMCS-2(1:3)2006
Volume: Volume 2, Issue 1
Published on: March 7, 2006
Submitted on: November 30, 2004
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,F.4.1


Share

Consultation statistics

This page has been seen 57 times.
This article's PDF has been downloaded 51 times.