An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic

DOI10.1112/plms/s3-69.1.1zbMath0799.03066OpenAlexW2133313069MaRDI QIDQ4308607

Jan Krajíček, Samuel R. Buss

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

zbMATH Keywords

proof theorybounded arithmeticdefinable functionsfragments of arithmeticBoolean complexitypolynomial local search

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)

Related Items (25)

The NP Search Problems of Frege and Extended Frege Proofs ⋮ Approximate counting and NP search problems ⋮ Circuit principles and weak pigeonhole variants ⋮ Relating the bounded arithmetic and polynomial time hierarchies ⋮ What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)? ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ On the complexity of finding falsifying assignments for Herbrand disjunctions ⋮ On the finite axiomatizability of ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ On the computational complexity of cut-reduction ⋮ Propositional proofs and reductions between NP search problems ⋮ 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 ⋮ A note on the Σ₁collection scheme and fragments of bounded arithmetic ⋮ Towards a unified complexity theory of total functions ⋮ Nested PLS ⋮ A Characterisation of Definable NP Search Problems in Peano Arithmetic ⋮ Induction rules in bounded arithmetic ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic ⋮ Separation results for the size of constant-depth propositional proofs ⋮ Some results on cut-elimination, provable well-orderings, induction and reflection ⋮ Ordinal notations and well-orderings in bounded arithmetic

This page was built for publication: An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic