Cook reducibility is faster than Karp reducibility in NP
From MaRDI portal
Publication:751812
DOI10.1016/0022-0000(90)90026-HzbMath0715.68030OpenAlexW1985343313MaRDI QIDQ751812
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
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
