Comparing Reductions to NP-Complete Sets

DOI10.1007/11786986_41MaRDI QIDQ3613782zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock, Aduri Pavan

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_41

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Comparing reductions to NP-complete sets
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• NP-completeness notions under strong hypotheses
• Strong reductions and isomorphism of complete sets
• scientific article; zbMATH DE number 1318517

Cited in

(16)

• Non-mitotic sets
• Strong nondeterministic Turing reduction - a technique for proving intractability
• Almost complete sets.
• On the reducibility of sets inside NP to sets with low information content
• The difference between polynomial-time many-one and truth-table reducibilities on distributional problems
• Non-uniform reductions
• Reductions between disjoint NP-pairs
• NE is not NP Turing reducible to nonexponentially dense NP sets
• Automatic Evaluation of Reductions between NP-Complete Problems
• scientific article; zbMATH DE number 1008510 (Why is no real title available?)
• Non-mitotic Sets
• Computing and Combinatorics
• Separating NP-completeness notions under strong hypotheses
• Cook reducibility is faster than Karp reducibility in NP
• Comparing reductions to NP-complete sets
• The complexity of unions of disjoint sets

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 Q3613782)