A note on complete problems for complexity classes

Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25)

Review text

Let \(\leq_{pm}\) and \(\leq_{pT}\) denote the polynomial-time bounded many-one and Turing reducibilities respectively. Clearly, every \(\leq_{pm}\)-complete set for some class will also be \(\leq_{pT}\)- complete for the class. This paper is concerned with determining when a class which has a \(\leq_{pT}\)-complete set also has a \(\leq_{pm}\)- complete set (now not necessarily the same set). Results of Ladner et al. tell us that this is not always the case. A main construction is presented for obtaining from any recursive set A a new recursive set A * which is polynomial-time bounded Turing equivalent to A (i.e., \(A\equiv_{pT}A\) *) and also satisfies \(\forall B\) \((B\leq_{pT}A\to B\leq_{pm}A\) *). This is fairly straightforward and uses a universal oracle machine \(M_ U(A)\) which on input 0 n1x computes \(M_ n(A)(x)\) in \(p(p_ n(x))\) steps for some polynomial p, where \(M_ n(A)\) is some standard recursive enumeration of oracle Turing machines with polynomial bounds \(p_ n.\) The main theorem then follows from this construction: For \({\mathcal C}^ a \)class of recursive sets closed under \(\equiv_{pT}\), \({\mathcal C}\) has a \(\leq_{pm}\)-complete set if \({\mathcal C}\) has a \(\leq_{pT}\)-complete set. The proof is simply a matter of checking that if A is \(\leq_{pT}\)- complete for \({\mathcal C}\) then A * is \(\leq_{pm}\)-complete for \({\mathcal C}.\) Some interesting corollaries which can now be proved are: \(\Delta\) \(p_ n\) has \(\leq_{pm}\)-complete sets. The class NP\(\cap co\)-NP has a \(\leq_{pm}\)-complete set iff it has a \(\leq_{pT}\)-complete set. Partial orderings of pm-degrees in \(\deg_{pT}(A)\) have a greatest element for any recursive set A. All proofs are clearly presented with just the correct amount of detail required.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: A note on complete problems for complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097029)