- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
The polynomial and linear time hierarchies in V0
Mathematical Logic Quarterly 55 (5):509-514 (2009)
Abstract
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 AjtaiDOI
10.1002/malq.200810007
My notes
Similar books and articles
The polynomial and linear hierarchies in models where the weak pigeonhole principle fails.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2008 - Journal of Symbolic Logic 73 (2):578-592.
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.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Higher type recursion, ramification and polynomial time.Stephen J. Bellantoni, Karl-Heinz Niggl & Helmut Schwichtenberg - 2000 - Annals of Pure and Applied Logic 104 (1-3):17-30.
On polynomial time computation over unordered structures.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2002 - Journal of Symbolic Logic 67 (3):1093-1125.
Deciding confluence of certain term rewriting systems in polynomial time.Guillem Godoy, Ashish Tiwari & Rakesh Verma - 2004 - Annals of Pure and Applied Logic 130 (1-3):33-59.
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.
Separations et transferts dans la hierarchie polynomiale des groupes abeliens lifinis.Ménard Bourgade - 2001 - Mathematical Logic Quarterly 47 (4):493-502.
Analytics
Added to PP
2013-12-01
Downloads
10 (#910,895)
6 months
1 (#478,598)
2013-12-01
Downloads
10 (#910,895)
6 months
1 (#478,598)
Historical graph of downloads
References found in this work
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
The polynomial and linear hierarchies in models where the weak pigeonhole principle fails.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2008 - Journal of Symbolic Logic 73 (2):578-592.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-5b5888c749-fsgz8 N