My question is as follows: Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$, where $A \leq _T^p B$ if there exists a polytime deterministic oracle machine that computes $A$ given access to $B$. That is, $A \leq _T ^p B$ if $A = M^B$ for some Turing machine $M$. I am getting stuck right at the start of the proof.

We have previously shown that there exists $B \in NP$ such that it is not $NP$-complete nor in $P$ by setting up a set of requirements and using delayed diagonalization. Given an $NP$-complete language $A$, and an enumeration of oracle polytime Turing machines $\{ M _e \}_{e\in \mathbb{N}}$, the requirements were $$R_{2e}: \exists y (A(y) \neq M_e^B(y)) \\ R_{2e + 1} : \exists y(B(y) \neq M_e(y)).$$

I want to try a similar strategy to build $A$ and $B$ in $NP$, thus having requirements $$ R_{2e} : \exists y (A(y) \neq M_e^B(y)) \\ R_{2e +1}: \exists y (B(y) \neq M_e^A(y)) $$

I don't really know how to start the process in this case, or if this is even the right method here. I would be thankful for some advice on how to continue or on a better strategy. Thanks in advance!


1 Answer 1


There is a well-known classical result of the theory of $p$-degrees stating that every non-zero $p$-T-degree splits into two incomparable $p$-T-degrees.

So assuming $P\neq NP$, by the splitting theorem, the $p$-T-degree of Turing-complete problem for $NP$ splits into two non-T-complete incomparable $p$-T-degrees.


Sublattices of the polynomial time degrees

LADNER, R. E. (1973), Polynomial time reducibility, in Proc. 5th Annual ACM Sympos. on Theory of Comput., pp. 122-129

LADNER, R. E. (1975), On the structure of polynomial time reducibility, J. Assoc. Comput. Math. 22, 155-171


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.