Propositional proofs and reductions between NP search problems

DOI10.1016/J.APAL.2012.01.015MaRDI QIDQ435190zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Nullstellensatzsearch problemspolynomial-time reducibilitypropositional proofs

Mathematics Subject Classification ID

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)

Recommendations

• On Search Problems in Complexity Theory and in Logic (Abstract)
• Towards a unified complexity theory of total functions
• The journey from NP to TFNP hardness
• The NP search problems of Frege and extended Frege proofs
• On the complexity of the parity argument and other inefficient proofs of existence

Cites work

• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 1114017 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• A tight relationship between generic oracles and type-2 complexity theory
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• An exponential separation between the parity principle and the pigeonhole principle
• Corrected upper bounds for free-cut elimination
• Herbrandizing search problems in Bounded Arithmetic
• How easy is local search?
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Separation results for the size of constant-depth propositional proofs
• The complexity of computing a Nash equilibrium
• The relative complexity of NP search problems

Cited in

(30)

• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Towards a unified complexity theory of total functions
• The Hairy Ball Problem is PPAD-Complete.
• Quasipolynomial size proofs of the propositional pigeonhole principle
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• Reductions in \textbf{PPP}
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Short proofs of the Kneser-Lovász coloring principle
• Theory and Applications of Models of Computation
• 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
• Propositional proofs in Frege and extended Frege systems (abstract)
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• 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)

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)