Valid proof regarding complexity class?

73 Views Asked by At

Consider $L \in BPP \cap NP$.

Every string $x \in L$ can be accepted with probability 2/3 since $L \in BPP$.

Every string $x \not \in L$ can be rejected with probability 1 since $L \in NP$.

This is the same definition as RP, so $L \in RP$ and $BPP \cap NP \subseteq RP$.

1

There are 1 best solutions below

0
On BEST ANSWER

This is incorrect. If $L$ were in $RP$, then there would be a deterministic TM that would accept with probability 2/3 on a correct input and reject with probability 1 on an incorrect input (along with a second input of random bits) in polynomial time.

You're correct that $BPP$ gives you the first condition, but $NP$ makes no guarantees about the second. It only says that there's a nondeterministic TM that accepts/rejects $x$ in polynomial time.

As of me writing this, the only known relationship between $NP$ and $RP$ is that $RP\subseteq NP$. Since it's also true that $RP\subseteq BPP$, then your conclusion would imply that $BPP\cap NP = RP$, which would be pretty significant.