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

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?

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

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

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)

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)

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.

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

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

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?