hardness vs. randomness paradigm Theorem: P != NP IFF P = BPP Theorem’: if SAT requires exponential time, then, we can show that P = BPP.