The relative complexity of NP search problems
From MaRDI portal
Publication:1273858
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
Related Items
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
