An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
From MaRDI portal
Publication:4308607
DOI10.1112/plms/s3-69.1.1zbMath0799.03066MaRDI QIDQ4308607
Publication date: 9 October 1994
Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/plms/s3-69.1.1
proof theory; bounded arithmetic; definable functions; fragments of arithmetic; Boolean complexity; polynomial local search
03D15: Complexity of computation (including implicit computational complexity)
03F30: First-order arithmetic and fragments
Related Items
The NP Search Problems of Frege and Extended Frege Proofs, Propositional proofs and reductions between NP search problems, Nested PLS, On the computational complexity of cut-reduction, The provably total NP search problems of weak second order bounded arithmetic, Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem, Alternating minima and maxima, Nash equilibria and bounded arithmetic, On the complexity of finding falsifying assignments for Herbrand disjunctions, Some results on cut-elimination, provable well-orderings, induction and reflection, Ordinal notations and well-orderings in bounded arithmetic, Relating the bounded arithmetic and polynomial time hierarchies, What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?, Circuit principles and weak pigeonhole variants, Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\), Separation results for the size of constant-depth propositional proofs, Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, A note on the Σ1collection scheme and fragments of bounded arithmetic, A Characterisation of Definable NP Search Problems in Peano Arithmetic
