# 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? 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. Apr 25, 2019 at 15:23
• I can't find any problems. so the assumption ∀A,B∈NP is redundant? 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$$.