Cook versus Karp-Levin: Separating completeness notions if NP is not small

DOI10.1016/0304-3975(95)00189-1zbMath0871.68083DBLPjournals/tcs/LutzM96OpenAlexW2080139332WikidataQ60578985 ScholiaQ60578985MaRDI QIDQ671427

Elvira Mayordomo, Jack H. Lutz

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://lib.dr.iastate.edu/cs_techreports/109

zbMATH Keywords

NP-completenessCook-completenessKarp-Levin completeness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (26)

NP-hard sets are superterse unless NP is small ⋮ Bi-immunity separates strong NP-completeness notions ⋮ Equivalence of measures of complexity classes ⋮ Unnamed Item ⋮ Genericity and measure for exponential time ⋮ Reductions between disjoint NP-pairs ⋮ An excursion to the Kolmogorov random strings ⋮ Nonuniform reductions and NP-completeness ⋮ A thirty year old conjecture about promise problems ⋮ A note on measuring in P ⋮ The size of SPP ⋮ Results on resource-bounded measure ⋮ Comparing reductions to NP-complete sets ⋮ Hard sets are hard to find ⋮ Unnamed Item ⋮ Martingale families and dimension in P ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ Nondeterminisic sublinear time has measure 0 in P ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 ⋮ On pseudorandomness and resource-bounded measure ⋮ Polylog depth, highness and lowness for E ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ On the Complexity of Inverse Mixed Integer Linear Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cook reducibility is faster than Karp reducibility in NP
• A comparison of polynomial time completeness notions
• Reductions on NP and p-selective sets
• Almost everywhere high nonuniform complexity
• On polynomial-time Turing and many-one completeness in PSPACE
• A comparison of polynomial time reducibilities
• Almost every set in exponential time is P-bi-immune
• Process complexity and effective random tests
• The density and complexity of polynomial cores for intractable sets
• Completeness, Approximation and Density
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Completeness for nondeterministic complexity classes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• The Complexity of Decision Versus Search
• Measure, Stochasticity, and the Density of Hard Languages
• Tally languages and complexity classes
• The Complexity and Distribution of Hard Problems
• [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung]
• A unified approach to the definition of random sequences

This page was built for publication: Cook versus Karp-Levin: Separating completeness notions if NP is not small