Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

In particular, impossibility results do not rule out approximate solutions that are good enough for practical purposes.


Unless it is an "impossibility of approximation" theorem.


Even that is frequently misleading. Take the problem of finding a maximum independent set. You can show that if you manage to approximate this problem within any constant factor then P = NP. On the other hand, finding large independent sets is a common subproblem in several graph reduction algorithms and simple heuristics often work very well on the graphs that occur in practice.




Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: