Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem

DOI10.1007/S00153-011-0240-0MaRDI QIDQ647334zbMATH OpenOpenAlexFDO

Authors Neil Thapen

Publication date 23 November 2011

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-011-0240-0

zbMATH Keywords

bounded arithmeticproof complexitysearch problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Recommendations

• The provably total search problems of bounded arithmetic
• scientific article; zbMATH DE number 1344922
• Bounded arithmetic, proof complexity and two papers of Parikh
• scientific article; zbMATH DE number 1070621
• Characterising definable search problems in bounded arithmetic via proof notations
• Herbrandizing search problems in Bounded Arithmetic
• scientific article; zbMATH DE number 819737
• Total search problems in bounded arithmetic and improved witnessing
• scientific article; zbMATH DE number 806753
• scientific article; zbMATH DE number 1670480

Cites work

• scientific article; zbMATH DE number 4145897 (Why is no real title available?)
• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 5038466 (Why is no real title available?)
• A form of feasible interpolation for constant depth Frege systems
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Bounded arithmetic and the polynomial hierarchy
• Characterising definable search problems in bounded arithmetic via proof notations
• Exponential lower bounds for the pigeonhole principle
• Fragments of bounded arithmetic and the lengths of proofs
• Herbrandizing search problems in Bounded Arithmetic
• Lifting independence results in bounded arithmetic
• NP search problems in low fragments of bounded arithmetic
• Notes on polynomially bounded arithmetic
• On induction-free provability
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• Polynomial size proofs of the propositional pigeonhole principle
• Quantified propositional calculi and fragments of bounded arithmetic
• Relating the bounded arithmetic and polynomial time hierarchies
• The provably total search problems of bounded arithmetic
• What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
• Witnessing functions in bounded arithmetic and search problems

Cited in

(6)

• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Witnessing flows in arithmetic
• NP search problems in low fragments of bounded arithmetic
• Witnessing functions in bounded arithmetic and search problems
• Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

This page was built for publication: Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem

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