An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic

DOI10.1112/plms/s3-69.1.1zbMath0799.03066MaRDI 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 theory; bounded arithmetic; definable functions; fragments of arithmetic; Boolean complexity; polynomial local search

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03F30: First-order arithmetic and fragments

Related Items

Approximate counting and NP search problems, On the finite axiomatizability of, The NP Search Problems of Frege and Extended Frege Proofs, Mining the surface: witnessing the low complexity theorems of arithmetic, 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, Towards a unified complexity theory of total functions, 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\)?, Induction rules in bounded arithmetic, 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, Typical forcings, NP search problems and an extension of a theorem of Riis, Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, A note on the Σ₁collection scheme and fragments of bounded arithmetic, A Characterisation of Definable NP Search Problems in Peano Arithmetic