In this question I ask about what use is a solver that can find an assignment that satisfies, say, 90% of the clauses of a known satisfiable 3SAT problem in polynomial time. The answer seems to be: given a problem ϕ that may or may not be satisfiable, you perform a reduction on an input formula ϕ to another formula ϕ′ such that ϕ′ is 90% satisfied iff ϕ is SAT and run my hypothetical algorithm on ϕ′, which will tell you if ϕ is SAT or not.

My question is a follow-up: what is the reduction from ϕ to ϕ'?


The reference is Håstad's classic paper, Some optimal inapproximability results. It relies on the PCP theorem and on Raz's parallel repetition theorem. The proof is not particularly easy, and even the reduction itself is not so simple to state (if you take into account the PCP component).

| cite | improve this answer | |
  • $\begingroup$ Okay, I started reading that paper and it scares me. I'm not a computer scientist by training, but I have taught myself Sipser's book. What do I need to learn in order to get through that paper? $\endgroup$ – Andrew Apr 2 '17 at 21:31
  • $\begingroup$ Mostly probability and analysis of Boolean functions. For the parallel repetition theorem you need some information theory. For the PCP theorem, depending on the proof, coding theory or expander graphs. $\endgroup$ – Yuval Filmus Apr 2 '17 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.