3 ms·

We don't know whether P = NP or not.

• jvanderbot 3y ago
  I 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 ago
      That makes sense! Thanks I felt like I'm perpetually a beginner when it comes to computational complexity theory