A question from homework 6

[Asaf]

Hello All

Homework 6, question 5:

"Prove that there is a constant c > 1 such that it is impossible to
approximate MAX-5-SAT in

polynomial-time within the factor c unless P = NP."


The proof in the answers is for MAX-E-5-SAT.
(I understand the proof and it's correctness).

My question is:
will the same proof work for MAX-5-SAT as well?

And if so, how?

Thanks',

Asaf.

[אריאל‎]

i believe the answer is yes, since the proof is by reduction from pcp,
and oco has two versions, E3SAT & 3SAT, so by reduction from 3SAT you
can proof that too.

[odedr]

There is a trivial reduction from MAX-E5-SAT to MAX-5-SAT (because the
former is a 'special case' of the latter), so if you show that the
former is hard to approximate, you also get that the latter is.

-- Oded