4
$\begingroup$

Assume that there exists at least one NP-intermediate decision problem (which, by Ladner's theorem, is equivalent to P being distinct from NP).

Do there exist two NP-intermediate decision problems, $A$ and $B$, such that neither one is polynomial-time reducible to the other?

$\endgroup$
  • 2
    $\begingroup$ In fact, it's known that in this case the NPI problems have a very rich structure; in particular, I think there are countably many pairwise non-reducible problems, as well as countably many tiers of intermediacy. I don't have any references to hand, but I can go digging a little later on. $\endgroup$ – Steven Stadnicki May 17 '18 at 15:56
4
$\begingroup$

Balcazar and Diaz proved that if $P \ne NP$ then there exists an infinite number of non-comparable languages in $NP$.

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