NP search problems in low fragments of bounded arithmetic

DOI10.2178/JSL/1185803628MaRDI QIDQ5294030zbMATH OpenOpenAlexFDO

Authors Jan Krajíček, Alan Skelley, Neil Thapen

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

bounded arithmeticresolutionsearch problems

Mathematics Subject Classification ID

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

Recommendations

• The provably total search problems of bounded arithmetic
• The provably total NP search problems of weak second order bounded arithmetic
• On the Structure of Bounded Queries to Arbitrary NP Sets
• Herbrandizing search problems in Bounded Arithmetic
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Total search problems in bounded arithmetic and improved witnessing
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• scientific article; zbMATH DE number 806753
• scientific article; zbMATH DE number 1344922

Cites work

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

Cited in

(25)

• Total search problems in bounded arithmetic and improved witnessing
• Towards a unified complexity theory of total functions
• Random resolution refutations
• Typical forcings, NP search problems and an extension of a theorem of Riis
• The provably total search problems of bounded arithmetic
• Characterising definable search problems in bounded arithmetic via proof notations
• Herbrandizing search problems in Bounded Arithmetic
• 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
• Approximate counting and NP search problems
• Resolution lower bounds for refutation statements
• Parity Games and Propositional Proofs
• The NP search problems of Frege and extended Frege proofs
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• Nested PLS
• Mining the surface: witnessing the low complexity theorems of arithmetic
• 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
• Witnessing flows in arithmetic
• TFNP intersections through the Lens of feasible disjunction
• A simple supercritical tradeoff between size and height in resolution
• Alternating minima and maxima, Nash equilibria and bounded arithmetic

This page was built for publication: NP search problems in low fragments of bounded arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5294030)