Cook reducibility is faster than Karp reducibility in NP (Q751812): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: The complexity of theorem-proving procedures / rank
 
Normal rank
Property / cites work
 
Property / cites work: A hierarchy for nondeterministic time complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Honest polynomial degrees and \(P=?NP\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Minimal degrees for polynomial reducibilities / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3862379 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some remarks on witness functions for nonpolynomial and noncomplete sets in NP / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4142699 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On one-way functions and polynomial-time isomorphisms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Completeness, Approximation and Density / rank
 
Normal rank
Property / cites work
 
Property / cites work: Collapsing degrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: A comparison of polynomial time reducibilities / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3915990 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the density of honest subrecursive classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Classification of the Recursive Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reductions among polynomial isomorphism types / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of unique solutions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recursively enumerable sets of positive integers and their decision problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5573961 / rank
 
Normal rank
Property / cites work
 
Property / cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reductions on NP and p-selective sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3819052 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A comparison of polynomial time completeness notions / rank
 
Normal rank

Revision as of 12:05, 21 June 2024

scientific article
Language Label Description Also known as
English
Cook reducibility is faster than Karp reducibility in NP
scientific article

    Statements

    Cook reducibility is faster than Karp reducibility in NP (English)
    0 references
    0 references
    1990
    0 references
    reducibility
    0 references
    NP-complete sets
    0 references

    Identifiers