Mathematical Logic Quarterly 55 (5):509-514 (2009)

We show that the bounded arithmetic theory V0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy . The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai
Keywords bounded arithmetic  linear hierarchy  bounded depth circuits  Prefix parity
Categories (categorize this paper)
DOI 10.1002/malq.200810007
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 64,209
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
¹1-Formulae on Finite Structures.M. Ajtai - 1983 - Annals of Pure and Applied Logic 24 (1):1.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Relating the Bounded Arithmetic and Polynomial Time Hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
A Decision Algorithm for Linear Sentences on a PFM.Lian Li, Huilin Li & Yixun Liu - 1993 - Annals of Pure and Applied Logic 59 (3):273-286.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Safe Recursion with Higher Types and BCK-Algebra.Martin Hofmann - 2000 - Annals of Pure and Applied Logic 104 (1-3):113-166.


Added to PP index

Total views
10 ( #877,811 of 2,455,143 )

Recent downloads (6 months)
1 ( #449,153 of 2,455,143 )

How can I increase my downloads?


My notes