A comparison of polynomial time completeness notions
From MaRDI portal
DOI10.1016/0304-3975(87)90132-0zbMATH Open0635.68035OpenAlexW2068655609WikidataQ56387788 ScholiaQ56387788MaRDI QIDQ1097692FDOQ1097692
Authors: 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
Recommendations
complexity classescompletenesspolynomial time reductionspolynomial time transformationsuperpolynomial decision problem classsuperpolynomial deterministic classes
Cites Work
- Title not available (Why is that?)
- Qualitative relativizations of complexity classes
- Title not available (Why is that?)
- The complexity of theorem-proving procedures
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- A comparison of polynomial time reducibilities
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Title not available (Why is that?)
- On one-one polynomial time equivalence relations
- Completeness, Approximation and Density
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Bi-immune sets for complexity classes
Cited In (17)
- Nontriviality for exponential time w.r.t. weak reducibilities
- On polynomial-time Turing and many-one completeness in PSPACE
- Structural analysis of the complexity of inverse functions
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- Comparing reductions to NP-complete sets
- On 1-truth-table-hard languages
- Completeness for nondeterministic complexity classes
- Cook reducibility is faster than Karp reducibility in NP
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Non-uniform reductions
- Weak completeness notions for exponential time
- The relative power of logspace and polynomial time reductions
- Exponential-time and subexponential-time sets
- Partial bi-immunity, scaled dimension, and NP-completeness
- Query-monotonic Turing reductions
- Almost complete sets.
This page was built for publication: A comparison of polynomial time completeness notions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097692)
