Hacker News new | past | comments | ask | show | jobs | submit login

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.




Join us for AI Startup School this June 16-17 in San Francisco!

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

Search: