3 ms·
> 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_approximation_scheme https://
by throwaway37585 8y ago
> 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_approximation_scheme https://en.m.wikipedia.org/wiki/Polynomial-time_approximatio...
- SolarNet 8y agoNot 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.
- throwaway37585 8y agoRight, but your statement was about NP hardness in general.