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

## 1 Answer

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$$.

It would not be very surprising to me for two NP-intermediate problems to be incomparable, but this would be very hard to prove, as we currently do not have a good idea of what problems even could be NP-intermediate. So, it would seem that the full answer to your question is an open problem, but if I had to guess then I'd guess the answer is no.