You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

evand comments on Post Request Thread - Less Wrong Discussion

20 Post author: Qiaochu_Yuan 11 April 2013 01:28AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (99)

You are viewing a single comment's thread. Show more comments above.

Comment author: evand 15 April 2013 04:18:18PM 0 points [-]

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,

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?