Hm...the set of NP-complete problems where there is a polynomial-time approximation scheme is not that large, and the approximation schemes can sometimes be pretty bad (i.e. getting answers within 1% takes time n^100). Besides, Bayesian inference is at least #P-complete, possibly P-space complete, and a 1% error in the prior blows up to arbitrarily large error in the posterior, so approximation algorithms won’t do anyways.
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?
Hm...the set of NP-complete problems where there is a polynomial-time approximation scheme is not that large, and the approximation schemes can sometimes be pretty bad (i.e. getting answers within 1% takes time n^100). Besides, Bayesian inference is at least #P-complete, possibly P-space complete, and a 1% error in the prior blows up to arbitrarily large error in the posterior, so approximation algorithms won’t do anyways.
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?