Strengths and Weaknesses of LH Arithmetic

Chris Pollett & Randall Pruim

In Pollett [3] a bounded arithmetic theory Z was shown not to be able to prove the collapse of the polynomial hierarchy. This theory also had the property that if Z ⊆ S_{2}^{i} for any i ≥ 1 then the polynomial hierarchy collapses. Here S_{2}^{i} are the theories of Buss [1]. Unfortunately, despite this property Z seemed too weak a theory to formalize many of the arguments that have been used in computational complexity. In this talk, we give a new arithmetic characterization of the levels of log-time hierarchy. Using this characterization, we propose a variant of the theory T AC^{0} of Clote and Takeuti [2]. This variant has nice deductive fragments which in some sense correspond to the levels of the log-time hierarchy. We show that this theory (like Z) cannot prove the collapse of the polynomial hierarchy. Furthermore, we give some evidence that this theory may be strong enough to prove that the log-time hierarchy is infinite, so unlike Z it can carry out useful complexity arguments.

[1] S. R. Buss. Bounded Arithmetic. Bibliopolis, Napoli, 1986.

[2] P. Clote and G. Takeuti. First order bounded arithmetic and small boolean circuit complexity classes. In P. Clote and J. Remmel, editors, Feasible Mathematics II, pages 154–218. Birkhäuser, Boston, 1995.

[3] C. Pollett. Multifunction algebras and the provability of P H ↓. Annals of Pure and Applied Logic, 104(1-3):279–303, Sept. 2000

Addresses Chris Pollett: Dept. of Mathematics, 405 Hilgard Ave., Box 951555, University of California, Los Angeles, CA. 90095, USA

E-mail: cpollett@willow.math.ucla.edu

Randall Pruim: Department of Mathematics and Statistics, Calvin College, Grand Rapids, MI, USA

E-mail: rpruim@calvin.edu