$\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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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? $\endgroup$– John L.Commented Apr 25, 2019 at 14:09
-
$\begingroup$ @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. $\endgroup$– Mohsen GhorbaniCommented Apr 25, 2019 at 15:23
-
$\begingroup$ I can't find any problems. so the assumption ∀A,B∈NP is redundant? $\endgroup$– Mohsen GhorbaniCommented Apr 25, 2019 at 15:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Apr 26, 2019 at 13:39