Propositional proofs and reductions between NP search problems
DOI10.1016/J.APAL.2012.01.015zbMATH Open1252.03127OpenAlexW2065828765MaRDI QIDQ435190FDOQ435190
Authors: Samuel R. Buss, Alan S. Johnson 
Publication date: 11 July 2012
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2012.01.015
Recommendations
Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Structure of proofs (03F07) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- How easy is local search?
- On the complexity of the parity argument and other inefficient proofs of existence
- On total functions, existence theorems and computational complexity
- The relative complexity of NP search problems
- The complexity of computing a Nash equilibrium
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Separation results for the size of constant-depth propositional proofs
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- A tight relationship between generic oracles and type-2 complexity theory
- An exponential separation between the parity principle and the pigeonhole principle
- Herbrandizing search problems in Bounded Arithmetic
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Title not available (Why is that?)
- Corrected upper bounds for free-cut elimination
Cited In (30)
- The Hairy Ball Problem is PPAD-Complete.
- Towards a unified complexity theory of total functions
- Quasipolynomial size proofs of the propositional pigeonhole principle
- Title not available (Why is that?)
- The complexity of gradient descent: CLS = PPAD \(\cap\) pls
- Reductions in \textbf{PPP}
- Theory and Applications of Models of Computation
- Short proofs of the Kneser-Lovász coloring principle
- Short proofs of the Kneser-Lovász coloring principle
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- The NP search problems of Frege and extended Frege proofs
- Reductions for non-clausal theorem proving
- Propositional proof systems based on maximum satisfiability
- Approximate counting and NP search problems
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Propositional proofs in Frege and extended Frege systems (abstract)
- Consistency of circuit evaluation, extended resolution and total NP search problems
- The journey from NP to TFNP hardness
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Integer factoring and modular square roots
- Minimum propositional proof length is NP-hard to linearly approximate
- Towards a Unified Complexity Theory of Total Functions
- PPAD-complete approximate pure Nash equilibria in Lipschitz games
- Note on constrained long choice with multiple beginning elements
- Automatic Evaluation of Reductions between NP-Complete Problems
- The Hairy Ball problem is PPAD-complete
- On Search Problems in Complexity Theory and in Logic (Abstract)
- The classes PPA-\(k\): existence from arguments modulo \(k\)
This page was built for publication: Propositional proofs and reductions between NP search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q435190)
