# for two languages in $NP$ does one of them karp reducible to another?

$$\forall A, B \in NP \implies A<_m^{poly}B. \lor B<_m^{poly} A.$$

I want to know is there any work around this theorem? or is it correct?

• Can you add an example of two languages that are not necessarily in NP such that neither one is not Karp reducible to the other? Commented Apr 25, 2019 at 14:09
• @Apass.Jack It's interesting! even complete languages in EXPSPACE are reducible to each other by polynomial karp reductions! I can't see karp reduction between one of these problems(EXPSPACE) into decidable languages in p/poly. Commented Apr 25, 2019 at 15:23
• I can't find any problems. so the assumption ∀A,B∈NP is redundant? Commented Apr 25, 2019 at 15:41

The theorem, as stated, is false: if $$A=\emptyset$$ and $$B=\Sigma$$, then we cannot reduce either of them to the other. If take either of $$A,B$$ to be non-trivial problems in $$P$$, the claim is true, which is not hard to show (see here). If either of $$A,B$$ is NP-complete, then the claim also holds by definition of NP-hardness.
So, the only case left is for problems $$A,B\in NP-(NPC\cup P)$$, the NP-intermediate problems. Note that such problems exist if and only if $$P\neq NP$$.