NP search problems in low fragments of bounded arithmetic

DOI10.2178/jsl/1185803628zbMath1118.03051OpenAlexW2162177577MaRDI 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

resolutionbounded arithmeticsearch problems

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items

The NP Search Problems of Frege and Extended Frege Proofs ⋮ Approximate counting and NP search problems ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Parity Games and Propositional Proofs ⋮ A note on propositional proof complexity of some Ramsey-type statements ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ 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 ⋮ Towards a unified complexity theory of total functions ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Nested PLS ⋮ POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC ⋮ Unnamed Item ⋮ 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 ⋮ Random resolution refutations ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic

Cites Work

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