A note on complete problems for complexity classes (Q1097029): Difference between revisions

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.