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

> You can't make even that kind of guarantee in the face of NP hardness.

You can. https://en.m.wikipedia.org/wiki/Polynomial-time_approximatio...



Not in the face of generic NP hardness. From your own link, even NP completeness is not enough.

> Any strongly NP-hard [which may include strongly NP-complete] optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP

I was criticizing someone for claiming the author's work is pointless. The author's work is an attempt to find a complexity class for markets (and the problem they solve). If we know the complexity class then maybe there is a PTAS. But without the author's work you can't begin to claim there is an epsilon.


Right, but your statement was about NP hardness in general.




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

Search: