Comparing reductions to NP-complete sets

DOI10.1016/J.IC.2006.10.005MaRDI QIDQ879596zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

polynomial-size circuitsdeterministic reductionsnonadaptive reductions

Mathematics Subject Classification ID

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

Recommendations

• Comparing Reductions to NP-Complete Sets
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• scientific article; zbMATH DE number 1318517
• A note on complete problems for complexity classes
• NP-completeness notions under strong hypotheses

Cites work

• scientific article; zbMATH DE number 1222922 (Why is no real title available?)
• scientific article; zbMATH DE number 1346358 (Why is no real title available?)
• scientific article; zbMATH DE number 1072532 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• A comparison of polynomial time completeness notions
• Almost everywhere high nonuniform complexity
• Bi-immunity separates strong NP-completeness notions
• Complete Problems and Strong Polynomial Reducibilities
• Completeness for nondeterministic complexity classes
• Compressibility and resource bounded measure
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Easy sets and hard certificate schemes
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Inverting onto functions.
• NP-hard sets are superterse unless NP is small
• On Isomorphisms and Density of NP and Other Complete Sets
• On gamma-reducibility versus polynomial time many-one reducibility
• Partial bi-immunity, scaled dimension, and NP-completeness
• Reducing the complexity of reductions
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Resource bounded randomness and weakly complete problems
• Separating NP-completeness notions under strong hypotheses
• Separation of NP-completeness notions
• Strong nondeterministic Turing reduction - a technique for proving intractability

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
• Comparing Reductions to NP-Complete Sets
• scientific article; zbMATH DE number 1688354 (Why is no real title available?)
• Separating NP-completeness notions under strong hypotheses
• Automatic Evaluation of Reductions between NP-Complete Problems
• scientific article; zbMATH DE number 3889514 (Why is no real title available?)
• Reductions between disjoint NP-pairs
• Nonuniform reductions and NP-completeness
• 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)