A comparison of polynomial time completeness notions
From MaRDI portal
(Redirected from Publication:1097692)
Several types of polynomial time reductions for the superpolynomial decision problem class \(DEXT=\cup \{DTIME(2^{cn})|\) \(c>0\}\) are considered. The purpose of the paper is to characterize the differences between polynomial time completeness notions for DEXT with respect to any pair of the above reductions. The author succeeds to prove all but two differences for the class DEXT. An interesting open problem is whether or not the obtained results hold also for complexity classes specified by nondeterministic machines.
Recommendations
Cites work
- A comparison of polynomial time reducibilities
- Bi-immune sets for complexity classes
- Completeness, Approximation and Density
- 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?)
- 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)- On polynomial-time Turing and many-one completeness in PSPACE
- Exponential-time and subexponential-time sets
- On 1-truth-table-hard languages
- The relative power of logspace and polynomial time reductions
- Almost complete sets.
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- Non-uniform reductions
- Weak completeness notions for exponential time
- Query-monotonic Turing reductions
- Partial bi-immunity, scaled dimension, and NP-completeness
- Nontriviality for exponential time w.r.t. weak reducibilities
- Completeness for nondeterministic complexity classes
- Structural analysis of the complexity of inverse functions
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- Cook reducibility is faster than Karp reducibility in NP
- Comparing reductions to NP-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)
