My general impression (having studied computer science, and complexity theory in passing, but being far from an expert) is that bounded-error approximations are not as well studied as precise solutions. I also get the impression that most of the bounded-error complexity results are results for specific approximation algorithms, not proofs about the limits of such algorithms. Are impossibility results for bounded-error approximations common?
In other words,
the set of NP-complete problems where there is a polynomial-time approximation scheme is not that large
Do you mean the set where such approximations are known, or the set where they are not known to be impossible?
I’m curious to learn more.
My general impression (having studied computer science, and complexity theory in passing, but being far from an expert) is that bounded-error approximations are not as well studied as precise solutions. I also get the impression that most of the bounded-error complexity results are results for specific approximation algorithms, not proofs about the limits of such algorithms. Are impossibility results for bounded-error approximations common?
In other words,
Do you mean the set where such approximations are known, or the set where they are not known to be impossible?