Cook reducibility is faster than Karp reducibility in NP
type: Item
instance of: scholarly article
title: Cook reducibility is faster than Karp reducibility in NP
zbMATH Open document ID: 0715.68030
DOI: 10.1016/0022-0000(90)90026-H
author: D. Kharzeev
published in: Journal of Computer and System Sciences
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4178764
zbMATH Keywords: reducibility
zbMATH Keywords: NP-complete sets
MaRDI profile type: Publication
cites work: The complexity of theorem-proving procedures
cites work: A hierarchy for nondeterministic time complexity
cites work: Q4198056
cites work: Honest polynomial degrees and \(P=?NP\)
cites work: Minimal degrees for polynomial reducibilities
cites work: Q3862379
cites work: Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
cites work: Q4142699
cites work: On one-way functions and polynomial-time isomorphisms
cites work: Completeness, Approximation and Density
cites work: Collapsing degrees
cites work: A comparison of polynomial time reducibilities
cites work: Q3915990
cites work: On the density of honest subrecursive classes
cites work: A Classification of the Recursive Functions
cites work: Reductions among polynomial isomorphism types
cites work: On the complexity of unique solutions
cites work: Recursively enumerable sets of positive integers and their decision problems
cites work: Q5573961
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: Reductions on NP and p-selective sets
cites work: Q3819052
cites work: A comparison of polynomial time completeness notions
full work available at URL: 0022-0000(90)90026-h
OpenAlex ID: W1985343313
description: scientific article; zbMATH DE number 4178764