Talk:(SAT, ε-UNSAT)

From Wikipedia, the free encyclopedia

So if (SAT, epsilon-UNSAT) is NP-hard, and by the PCP theorem, it's in PCP(log, constant), and the PCP theorem says that PCP(log, constant) = NP, then doesn't that mean that this decision problem is in NP, and therefore NP-complete? Normally NP-hard is only used for problems that aren't known to be in NP.

---

I need convincing this problem is NP-hard in the first place... —Preceding unsigned comment added by 68.49.170.91 (talk) 21:13, 3 October 2007 (UTC)