Witnessing functions in bounded arithmetic and search problems

DOI10.2307/2586729zbMath0919.03044OpenAlexW2056827464MaRDI QIDQ4227882

Jan Krajíček, Mario Chiari

Publication date: 19 August 1999

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

Full work available at URL: https://semanticscholar.org/paper/29754fa513d7bf043277c59e36c1fa9c2a56d13a

zbMATH Keywords

computational complexitymultifunctionsbounded arithmeticseparationsearch problemscomplexity classeswitnessing theoremsweak subsystems of first-order arithmetic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Approximate counting and NP search problems ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ The Ordering Principle in a Fragment of Approximate Counting ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Induction rules in bounded arithmetic ⋮ Random resolution refutations

Cites Work

• Exponential lower bounds for the pigeonhole principle
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On the scheme of induction for bounded arithmetic formulas
• Bounded arithmetic and the polynomial hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Quantified propositional calculi and fragments of bounded arithmetic
• The relative efficiency of propositional proof systems
• Provability of the pigeonhole principle and the existence of infinitely many primes
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

This page was built for publication: Witnessing functions in bounded arithmetic and search problems