5 ms·
BPP is the complexity class for decision problems that a randomized algorithm can solve in polynomial time, in the sense that on every input (worst-case), the a
by bo1024 3y ago
BPP is the complexity class for decision problems that a randomized algorithm can solve in polynomial time, in the sense that on every input (worst-case), the algorithm is right with at least 2/3 probability (over its own randomness).
One example is deciding whether a given number is prime. For a long time, we knew randomized algorithms like the Miller-Rabin test that are correct with high probability. That is, we knew PRIMES is in BPP. But we didn't know a deterministic algorithm. In 2006, a deterministic algorithm was discovered, proving that PRIMES is in P.
One of the central open problems in Computer Science is whether BPP=P. That is, for any problem we can solve with randomness (in the above sense), can we solve it without randomness? Among many other contributions, Wigderson's work has made a ton of progress toward this problem.
The general idea is to try to "derandomize" any randomized algorithm that runs in polynomial time and is correct with 2/3 probability. We will feed it inputs from a pseudorandom generator (instead of true random numbers). If the PRG is really really good, then we can get a deterministic algorithm by running the original algorithm along with the PRG.
Now, if we can prove certain problems are hard, then we can also prove that such really really good PRGs exist. This is basically because telling apart the PRG from true randomness would be a computationally hard problem.
- pulisse 3y ago> BPP is the complexity class for decision problems that a randomized algorithm can solve in polynomial time, in the sense that on every input (worst-case), the algorithm is right with at least 2/3 probability (over its own randomness). What's the theoretical significance of the 2/3 threshold?
- thehumanmeat 3y agoNone, it can actually be any constant > 1/2, because you can always run the algorithm a non-exponential number of more times to be more convinced (approaching prob 1) of the answer. 2/3 is just convention.
- jvanderbot 3y agoDumb question: There exist randomized approximation algorithms for Weighted Hitting Set, yet it is NP-Hard. Assuming I haven't said anything dumb yet, this surely should satisfy it: Why does this not prove BPP != P? Perhaps: Am I incorrect in assuming that randomized 2-approximation is somehow transformable to 'correctness in the decision problem 2/3 of the time'?
- JohnKemeny 3y agoWe don't know whether P = NP or not.
- jvanderbot 3y agoI realize that, but can you help me see why that's relevant here? The question as I understood it was BPP?=P, and I read that as "Do all problems that seem hard but have randomized algorithms actually live in P?" for which a counter example would be an NP-Hard problem with good randomized solution, right?
- bo1024 3y ago(Not who you asked, but) one important point here is definitely that BPP is about yes/no decision problems, and approximation algorithms are generally a different beast.
- jvanderbot 3y agoThat makes sense! Thanks I felt like I'm perpetually a beginner when it comes to computational complexity theory
- bo1024 3y ago> Perhaps: Am I incorrect in assuming that randomized 2-approximation is somehow transformable to 'correctness in the decision problem 2/3 of the time'? Yes, that's the issue. For another example, Max-Cut is NP-hard. We can easily get a randomized 2-approximation by taking a cut in the graph uniformly at random (don't even look at the graph structure). But it doesn't look possible to go from this totally random 2-approximation to a correct guess about the size of the true max cut.