Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 10 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
4  
2004 Survey by Luca Trevisan on inapproximability: cs.berkeley.edu/~luca/pubs/inapprox.ps –  Joel David Hamkins Jul 8 '10 at 3:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.