New answers tagged


The constant $1/3$ is completely arbitrary. Let's say that $\mathsf{BPP}_p$ is the class of problems solvable in polytime with error at most $p$. Then $\mathsf{BPP}_p = \mathsf{BPP}_q$ for any $0 < p,q < 1/2$. The simple proof can be found in any decent textbook or lectures notes on complexity theory, and is also a nice exercise. The idea is that you ...

Top 50 recent answers are included