Witnessing functions in bounded arithmetic and search problems
From MaRDI portal
Recommendations
- Total search problems in bounded arithmetic and improved witnessing
- The provably total search problems of bounded arithmetic
- scientific article; zbMATH DE number 733384
- Herbrandizing search problems in Bounded Arithmetic
- Characterising definable search problems in bounded arithmetic via proof notations
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- scientific article; zbMATH DE number 1344922
- scientific article; zbMATH DE number 1114024
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- scientific article; zbMATH DE number 1070621
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Bounded arithmetic and the polynomial hierarchy
- Exponential lower bounds for the pigeonhole principle
- On the scheme of induction for bounded arithmetic formulas
- Parity, circuits, and the polynomial-time hierarchy
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Quantified propositional calculi and fragments of bounded arithmetic
- The relative efficiency of propositional proof systems
Cited in
(17)- Total search problems in bounded arithmetic and improved witnessing
- Induction rules in bounded arithmetic
- Random resolution refutations
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- The ordering principle in a fragment of approximate counting
- Characterising definable search problems in bounded arithmetic via proof notations
- Fragments of Bounded Arithmetic and Bounded Query Classes
- Herbrandizing search problems in Bounded Arithmetic
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- A Characterisation of Definable NP Search Problems in Peano Arithmetic
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Approximate counting and NP search problems
- Computer Science Logic
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
This page was built for publication: Witnessing functions in bounded arithmetic and search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4227882)
