Comparing reductions to NP-complete sets
type: Item
instance of: scholarly article
title: Comparing reductions to NP-complete sets
zbMATH Open document ID: 1115.68088
author: John M. Hitchcock
author: Aduri Pavan
published in: Information and Computation
publication date: 2007-05-14T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5152424
zbMATH Keywords: nonadaptive reductions
zbMATH Keywords: deterministic reductions
zbMATH Keywords: polynomial-size circuits
MaRDI profile type: Publication
full work available at URL: j.ic.2006.10.005
OpenAlex ID: W2144718727
cites work: Cook versus Karp-Levin: Separating completeness notions if NP is not small
cites work: A comparison of polynomial time completeness notions
cites work: Completeness for nondeterministic complexity classes
cites work: Separating NP-completeness notions under strong hypotheses
cites work: Bi-immunity separates strong NP-completeness notions
cites work: Partial bi-immunity, scaled dimension, and NP-completeness
cites work: Q4359463
cites work: Q4218523
cites work: Q4266481
cites work: Separation of NP-completeness notions
cites work: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
cites work: Compressibility and resource bounded measure
cites work: NP-hard sets are superterse unless NP is small
cites work: Strong nondeterministic Turing reduction - a technique for proving intractability
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Complete Problems and Strong Polynomial Reducibilities
cites work: Almost everywhere high nonuniform complexity
cites work: Resource bounded randomness and weakly complete problems
cites work: Inverting onto functions.
cites work: Easy sets and hard certificate schemes
cites work: On gamma-reducibility versus polynomial time many-one reducibility
cites work: Q4359459
cites work: Reductions in circuit complexity: An isomorphism theorem and a gap theorem
cites work: Reducing the complexity of reductions
DOI: 10.1016/J.IC.2006.10.005
description: scientific article; zbMATH DE number 5152424