Cook reducibility is faster than Karp reducibility in NP

DOI10.1016/0022-0000(90)90026-HzbMath0715.68030OpenAlexW1985343313MaRDI QIDQ751812

D. Kharzeev

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(90)90026-h

zbMATH Keywords

reducibilityNP-complete sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Reductions among polynomial isomorphism types ⋮ A comparative study on the convergence rate of some iteration methods involving contractive mappings ⋮ Bi-immunity separates strong NP-completeness notions ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Partial bi-immunity, scaled dimension, and NP-completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Honest polynomial degrees and \(P=?NP\)
• A comparison of polynomial time completeness notions
• On one-way functions and polynomial-time isomorphisms
• Collapsing degrees
• Reductions on NP and p-selective sets
• A comparison of polynomial time reducibilities
• On the density of honest subrecursive classes
• A hierarchy for nondeterministic time complexity
• On the complexity of unique solutions
• Minimal degrees for polynomial reducibilities
• Completeness, Approximation and Density
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• A Classification of the Recursive Functions
• The complexity of theorem-proving procedures
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Cook reducibility is faster than Karp reducibility in NP