Gap clique

[guy paskar]

Hi,

Seems the reduction shown in the lecture, Gap_E3SAT[a,b] < Gap_maxClique[a,b] does not maintain the exact same gap 

(even though it's said that it does),  but rather turns [a,b] to [a/7,b/7].

So why does Gap_E3SAT[a,b] < Gap_maxClique[a,b] hold?

thanks...

[Yairh]

I don't think it holds

Gap_maxclique is easy for b=1

[Ran Zvilik]

תלוי באיזו רדוקצייה משתמשים. אפשר לעשות רדוקצייה כך שהפרמטרים ייחולקו
ב-3 ולא בשבע כמו שהזכרת כאן.
אבל אני לא חושב שיש רדוקצייה כך שהפרמטרים המקוריים יישמרו ללא שינוי.

[eyalg]

עדיין לא הבנתי, ראינו שיש כל מיני רדוקציות שמשנות את הפרמטרים (חלקי 3
או חלקי 7). אבל בכל מקרה שרשרת הרדוקציות האלו התחילה מבעיית 3SAT שלה
יש פרמטרים קבועים, ואחרי כמה רדוקציות, שבסך הכל משנים את הפרמטרים עד
כדי הכפלה בקבוע, אנו מקבלים שבעיית קליק לא ניתנת לקירוב בכל פקטור
קבוע.
אז השאלה היא כזאת, נניח שלבעיית קליק יש פרמטרים אלפא, ביתא קבועים
כלשהם (התחלנו מהקבועים של בעיית 3SAT וחילקנו/הכפלנו בקבועים).
אנו מכירים את המשפט שבעיית GAP עם פרמטרים אלפא ביתא, ניתנת לקירוב עד
כדי ביתא חלקי אלפא פחות אפסילון. יוצא מזה שאפשר לקרב את קליק בפקטור
קבוע.
איפה הטעות שלי?

> > > thanks...-הסתר טקסט מצוטט-
>
> -הראה טקסט מצוטט-

[Ran Zvilik]

לא הבנת נכון את המשפט.
הוא אומר שאם בעיית פער היא
NP-קשה
אז קשה לקרב אותה בכל פקטור שקטן מבטא חלקי אלפא, לא שניתן לקרב אותה בכל
פקטור קטן מבטא חלקי אלפא. וגם זה לא בהכרח אומר משהו לגבי הקירובים
שגדולים מבטא חלקי אלפא כמו שאפשר ללמוד מהמקרה של IS