Propositional proofs and reductions between NP search problems

DOI10.1016/j.apal.2012.01.015zbMath1252.03127OpenAlexW2065828765MaRDI QIDQ435190

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

Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Structure of proofs (03F07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity of proofs (03F20)

Related Items

Short Proofs of the Kneser-Lovász Coloring Principle ⋮ Approximate counting and NP search problems ⋮ Short proofs of the Kneser-Lovász coloring principle ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ Integer factoring and modular square roots ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ The Hairy Ball problem is PPAD-complete ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Propositional proof systems based on maximum satisfiability ⋮ Towards a unified complexity theory of total functions ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Unnamed Item ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle

Cites Work

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