Does NP = "epsilon-P" (PTAS / BPP)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T23:02:23Z http://mathoverflow.net/feeds/question/30989 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30989/does-np-epsilon-p-ptas-bpp Does NP = "epsilon-P" (PTAS / BPP)? Sai Emrys 2010-07-08T02:46:05Z 2010-07-09T08:42:12Z <p>Some NP-complete optimization problems, like the knapsack problem, have a solution reachable in polynomial time that is guaranteed to be within arbitrary &epsilon; of the optimum answer. (aka PTAS - polynomial time approximation scheme)</p> <p>Some decision problems, like testing primes, have probabilistic solutions (like Rabin's) where you can get to arbitrary &epsilon; certainty of having the right answer. (aka BPP - bounded error, probabilistic, polynomial time)</p> <p>I'm aware these are very different things theoretically, but I'm going to lump them together and call them "&epsilon;-P" - i.e. problems that have 'approximate' (in certainty or optimality) solutions in polynomial time, to within whatever &epsilon; one wants.</p> <p>My question is, how many NP problems are "&epsilon;-P", like the above?</p> <hr> <p>Answer as I understand it: </p> <p>Certain problems that are "MAX SNP-hard" have no PTAS. These include: metric traveling salesman, maximum bounded common induced subgraph, three dimensional matching, maximum H-matching, MAX-3SAT, MAX-CUT, vertex cover, and independent set.</p> <p>NP-complete problems probably don't have BPPs.</p> <p>However, there's no clear <em>positive</em> answer (i.e. what NP problems <em>do</em> have a PTAS/BPP). Brownie points if you can supply one.</p> <hr> <p>FYI: I am not a mathematician. (My areas are social neuroscience, computer hacking, etc.)</p> <p>So this is probably not nearly precisely characterized enough to answer precisely, and I am not able to do so. I'm going to give a motivated explanation; please fill in the gaps and correct my errors as you see fit. My boyfriend is a mathematician (algebraic combinatorics) and can translate stuff that's over my head, so don't feel obliged to talk down to me.</p> <p>This is a pragmatic rather than theoretical question (motivated purely by curiosity), so 'good-enough' answers are good enough. ;-)</p> http://mathoverflow.net/questions/30989/does-np-epsilon-p-ptas-bpp/30990#30990 Answer by Greg Kuperberg for Does NP = "epsilon-P" (PTAS / BPP)? Greg Kuperberg 2010-07-08T02:57:08Z 2010-07-08T02:57:08Z <p>One answer is that many of them aren't, by the <a href="http://en.wikipedia.org/wiki/Hardness_of_approximation" rel="nofollow">PCP theorem</a>. This was a dramatic discovery of the early 1990s. Even the Traveling Salesman Problem does not have a PTAS unless P = NP. (See also the <a href="http://www.cs.princeton.edu/~arora/pubs/almss.ps" rel="nofollow">classic original paper</a>.)</p> http://mathoverflow.net/questions/30989/does-np-epsilon-p-ptas-bpp/30993#30993 Answer by Joel David Hamkins for Does NP = "epsilon-P" (PTAS / BPP)? Joel David Hamkins 2010-07-08T03:20:13Z 2010-07-08T03:20:13Z <p>If P=NP, then of course <em>every</em> NP problem will be in $\epsilon$-P. So we probably shouldn't expect any proofs that a particular NP problem is definitely not in $\epsilon$-P to show up here, as this would settle P $\neq$ NP.</p> <p>Meanwhile, as Greg has already noted, there are several instances of NP complete problems whose approximate versions are also NP complete. So under P $\neq$ NP, these would be negative instances. However, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.9127&amp;rep=rep1&amp;type=pdf" rel="nofollow">This 1992 thesis</a> by Viggo Kann explains several positive instances of the phenomenon.</p> http://mathoverflow.net/questions/30989/does-np-epsilon-p-ptas-bpp/31046#31046 Answer by Peter Shor for Does NP = "epsilon-P" (PTAS / BPP)? Peter Shor 2010-07-08T14:10:20Z 2010-07-08T14:10:20Z <p>The answer to this question is essentially given in previous answers, but I'll try to state it more completely. It really depends on the problem. All NP-complete problems are equivalent in how hard it is to find their exact solution, but they vary widely in how hard it is to approximate them. Many of them can be shown hard to approximate by using the PCP theorem. A few were known to be hard to approximate before the PCP theorem. There are many which have a polynomial time approximation scheme (PTAS), and so are "easy" to approximate (for some meaning of "easy"). A few have a fully polynomial time approximation scheme (FPTAS), and so are easy to approximate (for a much more satisfying meaning of "easy").</p> <p>There are no known NP-complete problems which have probabilistic algorithms (like primality testing does) -- this would imply BPP=NP, which is something that computer scientists think is very unlikely.</p>