The relative complexity of NP search problems

DOI10.1006/jcss.1998.1575zbMath0920.68051OpenAlexW2037028865MaRDI QIDQ1273858

Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi, Stephen A. Cook, P. W. Beame

Publication date: 13 September 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1575

zbMATH Keywords

NP search problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (33)

The NP Search Problems of Frege and Extended Frege Proofs ⋮ On the black-box complexity of Sperner's Lemma ⋮ Approximate counting and NP search problems ⋮ The computational complexity of iterated elimination of dominated strategies ⋮ Computing equilibria: a computational complexity perspective ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Integer factoring and modular square roots ⋮ A note on propositional proof complexity of some Ramsey-type statements ⋮ Fixed-Parameter Algorithms for the Kneser and Schrijver Problems ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Propositional proofs and reductions between NP search problems ⋮ The provably total NP search problems of weak second order bounded arithmetic ⋮ Many-one reductions and the category of multivalued functions ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ The Hairy Ball problem is PPAD-complete ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Towards a unified complexity theory of total functions ⋮ Type-two polynomial-time and restricted lookahead ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS ⋮ 2-D Tucker is PPA complete ⋮ Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies ⋮ Unnamed Item ⋮ The complexity of the parity argument with potential ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Adventures in monotone complexity and TFNP ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents ⋮ Discrete versions of the KKM lemma and their PPAD-completeness ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ A Sperner lemma complete for PPA

Cites Work

• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Complexity for type-2 relations
• How easy is local search?
• Self-witnessing polynomial-time complexity and prime factorization
• On the complexity of the parity argument and other inefficient proofs of existence
• A tight relationship between generic oracles and type-2 complexity theory
• One-way functions and the nonisomorphism of NP-complete sets
• Every Prime Has a Succinct Certificate

This page was built for publication: The relative complexity of NP search problems