שאלה 7, 2006בב

[kiri...@gmail.com]

How many problems are NP-hard:
(1)Gap-E3SAT[9/10 , 1]
(2)Gap-E3SAT[9/2006 , 10/2006]
(3)Gap-3SAT[9/10 , 1]
(4)Gap-3SAT[9/2006 , 10/2006]

the right solution is 4, why?

(1) is surly NP hard
(2) is easy and trivial, isn't that?
(3) is NP hard, why
(4) isn't it trivial as well?

so why (2) and (4) are hard?

also, why 3SAT is harder than E3SAT?

[kiri...@gmail.com]

מישהו ענה על זה במקום אחר בפורום

[odedr]

3SAT is not easier than E3SAT because you can reduce the latter to the
former using the trivial identity reduction. (In other words, E3SAT is
a 'subproblem' of 3SAT and hence cannot be more difficult)

Both (2) and (4) are hard, as you can see by an easy reduction from
3SAT (just add enough dummy clauses).

-- Oded

[odedr]

I meant to say "by a reduction from E3SAT[9/10,1]"

-- Oded

[Eugene]

נראה לי שאם לעשות רדוקציה מ-E3SAT ב-2 וב-4 אז הפתרון ב-GAP הזה הוא
טריוויאלי ולכן זה לא קשה. האם אני מפספס כאן משהו?

[odedr]

Sorry, my mistake: both E3SAT and 3SAT are of course easy for gap
[9/2006,10/2006] (because a random assignment satisfies 7/8 of clauses
in the former case, and at least 1/2 of clauses in the latter case). I
didn't see the original question so I don't know why they marked the
correct answer as 4 (maybe it's a mistake in the solution file).

-- Oded