= 27d567bc2d48d9f40e9ccc20ea370b15)
jsteinhardt comments on Post Request Thread - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (99)
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?