A comparison of polynomial time completeness notions

DOI10.1016/0304-3975(87)90132-0zbMath0635.68035OpenAlexW2068655609WikidataQ56387788 ScholiaQ56387788MaRDI QIDQ1097692

Osamu Watanabe

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90132-0

zbMATH Keywords

completenesscomplexity classespolynomial time reductionspolynomial time transformationsuperpolynomial decision problem classsuperpolynomial deterministic classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Completeness for nondeterministic complexity classes, Query-monotonic Turing reductions, Comparing reductions to NP-complete sets, Nontriviality for exponential time w.r.t. weak reducibilities, Structural analysis of the complexity of inverse functions, Non-uniform reductions, Almost complete sets., Cook versus Karp-Levin: Separating completeness notions if NP is not small, On polynomial-time Turing and many-one completeness in PSPACE, Partial bi-immunity, scaled dimension, and NP-completeness, Collapsing and separating completeness notions under average-case and worst-case hypotheses, Exponential-time and subexponential-time sets, On 1-truth-table-hard languages, Cook reducibility is faster than Karp reducibility in NP, Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Weak completeness notions for exponential time, The relative power of logspace and polynomial time reductions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Qualitative relativizations of complexity classes
• On one-one polynomial time equivalence relations
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• A comparison of polynomial time reducibilities
• Bi-immune sets for complexity classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of theorem-proving procedures