The Relative Complexity of NP Search Problems

1998/08/01 by Paul Beame, Stephen Cook, Jeff Edmonds +2 · 1 voice · 10 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #semigroups and automata theory

paper · doi:10.1006/jcss.1998.1575

openalex publication_date 1998/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

• How easy is local search?

Cited by

• A Characterization of Basic Feasible Functionals Through Higher-Order Rewriting and Tuple Interpretations
• On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
• Propositional proofs and reductions betweenNPsearch problems
• The complexity of splitting necklaces and bisecting ham sandwiches
• Consensus halving is PPA-complete
• Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
• Hardness of Approximation Between P and NP
• The Nature of Computation
• The Classes PPA-k: Existence from Arguments Modulo k
• On the complexity of the parity argument and other inefficient proofs of existence
• A Sperner lemma complete for PPA

Discussions

• Yes, the problem is PPA-complete. One can reduce to it the problem LONELY from Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The relative complexity of NP search proble [stackexchange, 9 points]