The provably total NP search problems of weak second order bounded arithmetic

DOI10.1016/j.apal.2010.12.002zbMath1256.03064OpenAlexW2053365988MaRDI QIDQ639650

Juan-Miguel Gracia

Publication date: 22 September 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2010.12.002

zbMATH Keywords

bounded arithmeticsearch problemssecond-order arithmetictwo-sorted

Mathematics Subject Classification ID

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

Related Items

The NP Search Problems of Frege and Extended Frege Proofs ⋮ Approximate counting and NP search problems ⋮ Short proofs of the Kneser-Lovász coloring principle ⋮ QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ The canonical pairs of bounded depth Frege systems ⋮ Bounded theories for polyspace computability ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Towards a unified complexity theory of total functions ⋮ Improved witnessing and local improvement principles for second-order bounded arithmetic ⋮ CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On theories of bounded arithmetic for \(\mathrm{NC}^1\)
• How easy is local search?
• The relative complexity of NP search problems
• What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
• The provably total search problems of bounded arithmetic
• POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• NP search problems in low fragments of bounded arithmetic
• Fragments of bounded arithmetic and the lengths of proofs
• Notes on polynomially bounded arithmetic