Herbrandizing search problems in Bounded Arithmetic
From MaRDI portal
Recommendations
- Witnessing functions in bounded arithmetic and search problems
- Herbrand consistency of some finite fragments of bounded arithmetical theories
- NP search problems in low fragments of bounded arithmetic
- The provably total NP search problems of weak second order bounded arithmetic
- Characterising definable search problems in bounded arithmetic via proof notations
Cited in
(15)- Circuit principles and weak pigeonhole variants
- Characterising definable search problems in bounded arithmetic via proof notations
- A Characterisation of Definable NP Search Problems in Peano Arithmetic
- Witnessing functions in bounded arithmetic and search problems
- Propositional proofs and reductions between NP search problems
- Incompleteness in the finite domain
- Tight bounds for blind search on the integers
- Approximate counting and NP search problems
- NP search problems in low fragments of bounded arithmetic
- Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
- On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories
- Fragments of bounded arithmetic and the lengths of proofs
- A note on propositional proof complexity of some Ramsey-type statements
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- On the complexity of finding falsifying assignments for Herbrand disjunctions
This page was built for publication: Herbrandizing search problems in Bounded Arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3159414)
