What are the consequences of proving some relation ($\subseteq$, $\subset$, $=$, or $\neq$) on one of the following, to the other?
- $P$ vs. $BPP$
- $P$ vs. $NP$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.