What are the consequences of proving some relation ($\subseteq$, $\subset$, $=$, or $\neq$) on one of the following, to the other?

  1. $P$ vs. $BPP$
  2. $P$ vs. $NP$
  • 1
    $\begingroup$ Note that $\subseteq$ holds trivially in both cases. Beyond that, this seems rather broad. Surely the P vs NP thing has been covered in other questions. $\endgroup$ – David Richerby Aug 31 '18 at 16:38
  • $\begingroup$ Indeed the $P \subseteq BPP$ relation is trivial. Although the P vs. NP questions is broadly covered, I haven't found any source that summarize the connection between those two questions. $\endgroup$ – Napoleon Aug 31 '18 at 20:44

It is trivial that $P$ is contained in $BPP$ and that $P$ is contained in BPP. There are of course, many consequences of resolving both of these questions (they wouldn't be major open problems if that weren't the case). There is an important relationship between resolving 1 and resolving 2: From the Sipser-Lautemann theorem https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem it follows that if $P = NP$, then $P=BPP$. Of course, we strongly believe that $P \neq NP$, and that $P = BPP$, so this isn't a direction of reasoning that is likely to be actually useful by itself.

| cite | improve this answer | |
  • $\begingroup$ Thank you! I aware of your result, is there any more consequences, e.g for $BPP = P$ on $P$ vs. $NP$? $\endgroup$ – Napoleon Sep 2 '18 at 22:07

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.