The relative complexity of NP search problems
From MaRDI portal
Recommendations
Cites work
- A tight relationship between generic oracles and type-2 complexity theory
- Complexity for type-2 relations
- Every Prime Has a Succinct Certificate
- How easy is local search?
- On the complexity of the parity argument and other inefficient proofs of existence
- One-way functions and the nonisomorphism of NP-complete sets
- Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
- Self-witnessing polynomial-time complexity and prime factorization
Cited in
(57)- A Sperner lemma complete for PPA
- Towards a unified complexity theory of total functions
- On the classification of NP-complete problems in terms of their correlation coefficient
- 2-D Tucker is PPA complete
- The complexity of the parity argument with potential
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Shellings from relative shellings, with an application to NP-completeness
- 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 Hairy Ball problem is PPAD-complete
- Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Structural complexity of multiobjective NP search problems
- Many-one reductions and the category of multivalued functions
- The computational complexity of iterated elimination of dominated strategies
- On Search Problems in Complexity Theory and in Logic (Abstract)
- scientific article; zbMATH DE number 5527901 (Why is no real title available?)
- scientific article; zbMATH DE number 1263206 (Why is no real title available?)
- Towards the Actual Relationship Between NP and Exponential Time
- The Complexity of Decision Versus Search
- Propositional proofs and reductions between NP search problems
- scientific article; zbMATH DE number 1072533 (Why is no real title available?)
- Towards a Unified Complexity Theory of Total Functions
- Approximate counting and NP search problems
- Adventures in monotone complexity and TFNP
- The Hairy Ball Problem is PPAD-Complete.
- Nullstellensatz size-degree trade-offs from reversible pebbling
- scientific article; zbMATH DE number 7561747 (Why is no real title available?)
- The NP search problems of Frege and extended Frege proofs
- Consistency of circuit evaluation, extended resolution and total NP search problems
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
- Complete and tractable machine-independent characterizations of second-order polytime
- A note on propositional proof complexity of some Ramsey-type statements
- The provably total NP search problems of weak second order bounded arithmetic
- Further collapses in \(\mathsf{TFNP}\)
- The complexity of gradient descent: CLS = PPAD pls
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Extended Nullstellensatz proof systems
- On basic feasible functionals and the interpretation method
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-Checker
- A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations
- Bounds on the total coefficient size of nullstellensatz proofs of the pigeonhole principle
- Intersection classes in TFNP and proof complexity
- TFNP intersections through the Lens of feasible disjunction
- The computational complexity of finding stationary points in non-convex optimization
- Separations in proof complexity and TFNP
- Strength and limitations of Sherali-Adams and nullstellensatz proof systems
- Complete and tractable machine-independent characterizations of second-order polytime
- Alternating minima and maxima, Nash equilibria and bounded arithmetic
- On the black-box complexity of Sperner's Lemma
- Computing equilibria: a computational complexity perspective
- Integer factoring and modular square roots
This page was built for publication: The relative complexity of NP search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1273858)
