4 ms·

This is a consequence of the PCP theorem, right? https://en.wikipedia.org/wiki/MAX-3SAT#Theorem_1_(inapproximability) https://en.wikipedia.org/wiki/MAX-3SAT#Th

• nhaehnle 9y ago
  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.)