An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic

DOI10.1112/PLMS/S3-69.1.1MaRDI QIDQ4308607zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Witnessing functions in bounded arithmetic and search problems
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• Fragments of Bounded Arithmetic and Bounded Query Classes
• scientific article; zbMATH DE number 806753
• Characterising definable search problems in bounded arithmetic via proof notations

Cited in

(33)

• Upper Bounds on Boolean-Width with Applications to Exact Algorithms
• Towards a unified complexity theory of total functions
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• Nested PLS
• Space bounded computations: Review and new separation results
• Boshernitzan’s condition, factor complexity, and an application
• A Characterisation of Definable NP Search Problems in Peano Arithmetic
• Fragments of Bounded Arithmetic and Bounded Query Classes
• Mining the surface: witnessing the low complexity theorems of arithmetic
• The NP search problems of Frege and extended Frege proofs
• Propositional proofs and reductions between NP search problems
• Approximate counting and NP search problems
• An unexpected separation result in Linearly Bounded Arithmetic
• A note on the \(\Sigma_1\) collection scheme and fragments of bounded arithmetic
• Typical forcings, NP search problems and an extension of a theorem of Riis
• On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• Circuit principles and weak pigeonhole variants
• Separation results for the size of constant-depth propositional proofs
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
• Relating the bounded arithmetic and polynomial time hierarchies
• On the computational complexity of cut-reduction
• The provably total NP search problems of weak second order bounded arithmetic
• Witnessing flows in arithmetic
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• scientific article; zbMATH DE number 1420845 (Why is no real title available?)
• Biabduction (and related problems) in array separation logic
• Induction rules in bounded arithmetic
• Some results on cut-elimination, provable well-orderings, induction and reflection
• Ordinal notations and well-orderings in bounded arithmetic
• What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4308607)