1
$\begingroup$

$\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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.