Comparing reductions to NP-complete sets

DOI10.1016/j.ic.2006.10.005zbMath1115.68088OpenAlexW2144718727MaRDI QIDQ879596

John M. Hitchcock, A. 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)

Related Items (6)

A note on VNP-completeness and border complexity ⋮ Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ Strong Reductions and Isomorphism of Complete Sets

Cites Work

• NP-hard sets are superterse unless NP is small
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• A comparison of polynomial time completeness notions
• On gamma-reducibility versus polynomial time many-one reducibility
• Almost everywhere high nonuniform complexity
• Strong nondeterministic Turing reduction - a technique for proving intractability
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Easy sets and hard certificate schemes
• Resource bounded randomness and weakly complete problems
• Inverting onto functions.
• Bi-immunity separates strong NP-completeness notions
• Partial bi-immunity, scaled dimension, and NP-completeness
• Compressibility and Resource Bounded Measure
• Separation of NP-Completeness Notions
• Completeness for nondeterministic complexity classes
• Complete Problems and Strong Polynomial Reducibilities
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Separating NP-completeness notions under strong hypotheses
• Reducing the complexity of reductions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Comparing reductions to NP-complete sets