- 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
NP Search Problems in Low Fragments of Bounded Arithmetic
Journal of Symbolic Logic 72 (2):649 - 672 (2007)
Abstract
We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories $T_{2}^{2}$ and $T_{3}^{2}$Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Witnessing functions in bounded arithmetic and search problems.Mario Chiari & Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (3):1095-1115.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Fragments of bounded arithmetic and the lengths of proofs.Pavel Pudl'ak - 2008 - Journal of Symbolic Logic 73 (4):1389-1406.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Finite automata, real time processes and counting problems in bounded arithmetics.Mirosław Kutyłowski - 1988 - Journal of Symbolic Logic 53 (1):243-258.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Analytics
Added to PP
2010-08-24
Downloads
26 (#589,939)
6 months
2 (#1,244,653)
2010-08-24
Downloads
26 (#589,939)
6 months
2 (#1,244,653)
Historical graph of downloads
Citations of this work
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
The provably total NP search problems of weak second order bounded arithmetic.Leszek Aleksander Kołodziejczyk, Phuong Nguyen & Neil Thapen - 2011 - Annals of Pure and Applied Logic 162 (6):419-446.
Typical forcings, NP search problems and an extension of a theorem of Riis.Moritz Müller - 2021 - Annals of Pure and Applied Logic 172 (4):102930.
Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.Pavel Pudlák & Neil Thapen - 2012 - Annals of Pure and Applied Logic 163 (5):604-614.
On the correspondence between arithmetic theories and propositional proof systems – a survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
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-7c76586df8-l2pxr uwo