An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic

DOI10.1112/PLMS/S3-69.1.1zbMATH Open0799.03066OpenAlexW2133313069MaRDI QIDQ4308607FDOQ4308607

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

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

zbMATH Keywords

proof theory bounded arithmetic definable functions fragments of arithmetic Boolean complexity polynomial local search

Mathematics Subject Classification ID

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

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
Approximate counting and NP search problems
Propositional proofs and reductions between NP search problems
An unexpected separation result in Linearly Bounded Arithmetic
A note on the \(\Sigma_1\) collection scheme and fragments of bounded arithmetic
On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
Typical forcings, NP search problems and an extension of a theorem of Riis
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
Title not available (Why is that?)
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)