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$

Question

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!

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.

REFERENCES

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