| Yes, the article is being a little vague with quantifiers. Let L be a language. L is in BPP if there exist a probabilistic, polynomial time TM such that: For every input x in L, M on x outputs YES with probability close to one. For every input x not in L, M outputs NO with probability close to one. Notice that the input is quantified by "for every" x. The probability in BPP (and thus the error) is only over the random coin tosses that the algorithm uses, not the inputs. This gives our intuition for BPP = P: we can completely eliminate the error using a sufficiently high-quality pseudorandom generator (PRG). We believe that P = BPP because we believe high-quality PRGs exist. More precisely, we can construct such PRGs if there are problems in exponential time that require exponential time even "with advice". Advice is arbitrary information associated with each input length of a problem -- it could even be uncomputable. That is, on all inputs of length n, I get access to a specific string of length poly(n), for instance. That's one string per input length mind, not per input -- if it was per input I could just give you the answer. So such a lower bound is like saying that a certain problem in exponential time is really exponential; there is no strange "compression scheme" that could give us some weird information about all inputs of length n and admit a sub-exponential time solution to the problem. Intuitively, it would be super weird if advice let us cut down on computation time so dramatically. Formally, there are strange consequences if advice is powerful. For instance, if NP is contained in P with polynomial-length advice, PH collapses to the second level (the Karp-Lipton Theorem). On Heuristics: A heuristic is a different notion of complexity: we would instead say for most inputs x, or for any efficiently sample-able distribution over inputs x, the algorithm is correct with high probability. This notion makes perfect sense when combined with deterministic algorithms or with randomized algorithms. In the deterministic setting, the probability is only over the inputs. In the randomized setting, we have a joint probability over inputs and tossed coins. |