# Does NP = “epsilon-P” (PTAS / BPP)?

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?

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

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.