Skip to main content
1 of 2
Slugger
  • 161
  • 3

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$

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!

Slugger
  • 161
  • 3