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

While what you're saying is technically true, you have to be careful with the exact definitions. For many NPC problems, approximations are indeed hard as well, but that a worst case statement. The existence of an algorithm that finds sufficiently good solutions for all instances implies P=NP, but that doesn't mean that there aren't algorithms that find very good approximations for all instances that occur in practice, or for almost all instances that you sample uniformly at random. As long as there is an arbitrarily obscure class of instances left where the algorithm fails to provide a good approximation P!=NP remains a possibility. Experimental evaluations of approximation ratios are not sufficient to claim P=NP.



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

Search: