Hacker News new | ask | show | jobs
by moyix 3099 days ago
This is a consequence of the PCP theorem, right?

https://en.wikipedia.org/wiki/MAX-3SAT#Theorem_1_(inapproxim...

1 comments

No. Many approximation problems are known to be NP-hard without relying on the PCP theorem. The PCP theorem is "only" one of the strongest (if not the strongest) and widely applicable result about approximation hardness. (I may be underselling it with this short summary because of the unique games conjecture; in any case, the main point is that there were approximation problems known to be hard long before the PCP theorem was found.)