NP search problems in low fragments of bounded arithmetic

DOI10.2178/jsl/1185803628zbMath1118.03051MaRDI QIDQ5294030

Alan Skelley, Neil Thapen, Jan Krajíček

Publication date: 9 July 2007

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.307.765

zbMATH Keywords

resolution; bounded arithmetic; search problems

Mathematics Subject Classification ID

03F30: First-order arithmetic and fragments

03F20: Complexity of proofs

Related Items

Unnamed Item, Approximate counting and NP search problems, Parity Games and Propositional Proofs, The NP Search Problems of Frege and Extended Frege Proofs, Mining the surface: witnessing the low complexity theorems of arithmetic, Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\), Nested PLS, A note on propositional proof complexity of some Ramsey-type statements, The provably total NP search problems of weak second order bounded arithmetic, Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem, Alternating minima and maxima, Nash equilibria and bounded arithmetic, Towards a unified complexity theory of total functions, Random resolution refutations, Typical forcings, NP search problems and an extension of a theorem of Riis, POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC, Examining Fragments of the Quantified Propositional Calculus, On the correspondence between arithmetic theories and propositional proof systems – a survey, A Characterisation of Definable NP Search Problems in Peano Arithmetic

Cites Work

• Lower bounds to the size of constant-depth propositional proofs
• A new proof of the weak pigeonhole principle