3 ms·
Dumb question: There exist randomized approximation algorithms for Weighted Hitting Set, yet it is NP-Hard. Assuming I haven't said anything dumb yet, this sure
by jvanderbot 3y ago
Dumb 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.