Does NP = "epsilon-P" (PTAS / BPP)? - MathOverflow

Does NP = "epsilon-P" (PTAS / BPP)?

2010-07-08T02:46:05Z

Some NP-complete optimization problems, like the knapsack problem, have a solution reachable in polynomial time that is guaranteed to be within arbitrary ε of the optimum answer. (aka PTAS - polynomial time approximation scheme)

Some decision problems, like testing primes, have probabilistic solutions (like Rabin's) where you can get to arbitrary ε certainty of having the right answer. (aka BPP - bounded error, probabilistic, polynomial time)

I'm aware these are very different things theoretically, but I'm going to lump them together and call them "ε-P" - i.e. problems that have 'approximate' (in certainty or optimality) solutions in polynomial time, to within whatever ε one wants.

My question is, how many NP problems are "ε-P", like the above?

Answer as I understand it:

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.

NP-complete problems probably don't have BPPs.

However, there's no clear positive answer (i.e. what NP problems do have a PTAS/BPP). Brownie points if you can supply one.

FYI: I am not a mathematician. (My areas are social neuroscience, computer hacking, etc.)

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.

This is a pragmatic rather than theoretical question (motivated purely by curiosity), so 'good-enough' answers are good enough. ;-)

Answer by Greg Kuperberg for Does NP = "epsilon-P" (PTAS / BPP)?

2010-07-08T02:57:08Z

One answer is that many of them aren't, by the PCP theorem. 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 classic original paper.)

Answer by Joel David Hamkins for Does NP = "epsilon-P" (PTAS / BPP)?

2010-07-08T03:20:13Z

If P=NP, then of course every 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.

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, This 1992 thesis by Viggo Kann explains several positive instances of the phenomenon.

Answer by Peter Shor for Does NP = "epsilon-P" (PTAS / BPP)?

2010-07-08T14:10:20Z

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").

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.