Propositional proofs and reductions between NP search problems
From MaRDI portal
Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Structure of proofs (03F07) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Recommendations
Cites work
- A tight relationship between generic oracles and type-2 complexity theory
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- An exponential separation between the parity principle and the pigeonhole principle
- Corrected upper bounds for free-cut elimination
- Herbrandizing search problems in Bounded Arithmetic
- How easy is local search?
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1114017 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- On the complexity of the parity argument and other inefficient proofs of existence
- On total functions, existence theorems and computational complexity
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Separation results for the size of constant-depth propositional proofs
- The complexity of computing a Nash equilibrium
- The relative complexity of NP search problems
Cited in
(33)- Short proofs of the Kneser-Lovász coloring principle
- Reductions in \textbf{PPP}
- Towards a unified complexity theory of total functions
- The Hairy Ball problem is PPAD-complete
- Propositional proof systems based on maximum satisfiability
- Quasipolynomial size proofs of the propositional pigeonhole principle
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Minimum propositional proof length is NP-hard to linearly approximate
- Automatic Evaluation of Reductions between NP-Complete Problems
- Propositional proofs in Frege and extended Frege systems (abstract)
- On Search Problems in Complexity Theory and in Logic (Abstract)
- Short proofs of the Kneser-Lovász coloring principle
- The journey from NP to TFNP hardness
- Towards a Unified Complexity Theory of Total Functions
- Approximate counting and NP search problems
- The Hairy Ball Problem is PPAD-Complete.
- 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\)
- Theory and Applications of Models of Computation
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Reductions for non-clausal theorem proving
- PPAD-complete approximate pure Nash equilibria in Lipschitz games
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- The complexity of gradient descent: CLS = PPAD pls
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Note on constrained long choice with multiple beginning elements
- Intersection classes in TFNP and proof complexity
- The computational complexity of finding stationary points in non-convex optimization
- Settling the complexity of Nash equilibrium in congestion games
- Integer factoring and modular square roots
This page was built for publication: Propositional proofs and reductions between NP search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q435190)
