Comparing reductions to NP-complete sets
From MaRDI portal
Publication:879596
DOI10.1016/J.IC.2006.10.005zbMATH Open1115.68088OpenAlexW2144718727MaRDI QIDQ879596FDOQ879596
John M. Hitchcock, Aduri Pavan
Publication date: 14 May 2007
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2006.10.005
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Almost everywhere high nonuniform complexity
- NP-hard sets are superterse unless NP is small
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Title not available (Why is that?)
- Completeness for nondeterministic complexity classes
- Resource bounded randomness and weakly complete problems
- Bi-immunity separates strong NP-completeness notions
- Separation of NP-completeness notions
- Separating NP-completeness notions under strong hypotheses
- Reducing the complexity of reductions
- A comparison of polynomial time completeness notions
- Title not available (Why is that?)
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- Title not available (Why is that?)
- Inverting onto functions.
- Complete Problems and Strong Polynomial Reducibilities
- Partial bi-immunity, scaled dimension, and NP-completeness
- On gamma-reducibility versus polynomial time many-one reducibility
- Strong nondeterministic Turing reduction - a technique for proving intractability
- Easy sets and hard certificate schemes
- Compressibility and resource bounded measure
- Title not available (Why is that?)
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Cited In (16)
- On the reducibility of sets inside NP to sets with low information content
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- A note on VNP-completeness and border complexity
- Autoreducibility of NP-complete sets under strong hypotheses
- Cook reducibility is faster than Karp reducibility in NP
- Strong Reductions and Isomorphism of Complete Sets
- Strong nondeterministic Turing reduction - a technique for proving intractability
- Title not available (Why is that?)
- Comparing Reductions to NP-Complete Sets
- Title not available (Why is that?)
- Separating NP-completeness notions under strong hypotheses
- Automatic Evaluation of Reductions between NP-Complete Problems
- Title not available (Why is that?)
- Reductions between disjoint NP-pairs
- Nonuniform reductions and NP-completeness
- Computing and Combinatorics
This page was built for publication: Comparing reductions to NP-complete sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879596)
