12
$\begingroup$

$RP = NP$ is widely conjectured to be false.

But imagine for a moment that it is true. In such case, how likely would be that $P = NP$?

Put in other words: in a world where $RP = NP$, what might still be seen as an obstacle for us to believe $P = NP$?

$\endgroup$
3
  • 3
    $\begingroup$ In other words, you are asking for an oracle relative to which RP=NP but P$\neq$NP. $\endgroup$ Jan 20 '13 at 22:44
  • $\begingroup$ Yes. I would like to know whether, in a world where $RP=NP$, the additional conditions that need to be true for $P\neq NP$ are more stringent and unlikely than the additional conditions that need to be true for $P=NP$. $\endgroup$ Jan 20 '13 at 22:50
  • 7
    $\begingroup$ @Yuval Filmus: I do not know whether the question is about relativization barrier, but if it is, then there is an oracle relative to which RP=EXP (which implies P≠RP=NP). I cannot find the reference for this fact now, but it is stated in the remark after Theorem 6 in Heller 1986 with references to two papers by Kurtz and by Heller, both in the proceedings of “Conference on Computational Complexity Theory” in March 1983. $\endgroup$ Jan 20 '13 at 23:08
14
$\begingroup$

Honestly speaking, I do not think that Stack Exchange is a suitable place to ask for a future prediction. Despite this, I will post a response because it is fun to play with the idea of fortune telling.

As far as I know, the possibility of P≠RP=NP has not been ruled out. Moreover, there is a language A such that RPA=EXPA [Hel83, Kur83], which immediately implies that PA≠RPA=NPA. (I have not checked [Hel83] or [Kur83], and I took the result and the references from the remark after Theorem 6 in [Hel86].) In other words, even proving the implication RP=NP ⇒ P=NP requires a nonrelativizing technique, and therefore it is understandable that this implication has not been proved.

(Lance Fortnow has discussed a similar result in the Computational Complexity blog: Oracle Results are Good For You.)

Now let’s turn to the fortune-telling part.

How much does this oracle result tell about the likeliness of P=NP in the world where RP=NP has been already proved? Not much. At the very least, it should not be taken as evidence that in the world where RP=NP has been proved, it is still likely to be difficult to prove P=NP. In such a world, some new, powerful nonrelativizing techniques are known to human, and therefore it would not be reasonable to interpret “requires a nonrelativizing technique” as evidence for difficulty.

Speaking more broadly, if RP=NP has been proved despite all the beliefs (and also proof technique barriers) against it, then our current intuitive understanding about efficient computation is likely to be very wrong. Obviously we cannot apply our current intuition to reason about the world where our current intuition fails spectacularly. I do not think that we can make an educated guess about such a world except for what has been rigorously proved.

References

[Hel83] Hans Heller. On relativized polynomial hierarchies extending to two levels. In Proceedings of Conference on Computational Complexity Theory, pp. 109–114, UC Santa Barbara, March 1983.

[Hel86] Hans Heller. On relativized exponential and probabilistic complexity classes. Information and Control, 71(3):231–243, Dec. 1986. DOI: 10.1016/S0019-9958(86)80012-2.

[Kur83] S. Kurtz (Stuart A. Kurtz?). The fine structure of NP: Relativizations. In Proceedings of Conference on Computational Complexity Theory, pp. 42–50, UC Santa Barbara, March 1983.

$\endgroup$
1
  • $\begingroup$ 'Obviously we cannot apply our current intuition to reason about the world where our current intuition fails spectacularly'.... this is a big statement. $\endgroup$
    – Mr.
    Dec 11 '16 at 0:25

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.