A comparison of polynomial time completeness notions
From MaRDI portal
(Redirected from Publication:1097692)
Recommendations
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3596249 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- A comparison of polynomial time reducibilities
- Bi-immune sets for complexity classes
- Completeness, Approximation and Density
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On one-one polynomial time equivalence relations
- Qualitative relativizations of complexity classes
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The complexity of theorem-proving procedures
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 versus Karp-Levin: Separating completeness notions if NP is not small
- Cook reducibility is faster than Karp reducibility in NP
- 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)
