שאלה פתוחה 2ג' מהמבחן cc06b-c,עם B4SAT

Yossi

unread,

Jul 1, 2009, 9:02:57 AM7/1/09

to Complexity Course, Spring 2009, Tel Aviv University

מישהו הצליח לענות עליה?

נגיד שהצבה מאוזנת עבור הסגר, אם בדיוק חצי מהליטרלים שלו מקבלים T.
B4SAT היא הבעיה הבאה:
קלט: נוסחת E4CNF (כלומר נוסחת CNF שבה בכל הסגר בדיוק 4 משתנים שונים
זה מזה).
מטרה: למצוא הצבה שהיא מאוזנת למספר מקסימלי של הסגרים.

ג. הראו שקיים קבוע c>0 כך שלקרב את B4SAT טוב יותר מ-c זו בעיה NP-hard.

yuval rochman

unread,

Jul 1, 2009, 10:16:12 AM7/1/09

to complexity-course-spring...@googlegroups.com

רדוקציה מNAE3-SAT:
לכל הסגר x1Vx2Vx3 נוסיף משתנה x4 ונקבל נוסחא x1Vx2Vx3Vx4.

2009/7/1 Yossi <joza...@gmail.com>

Gaby Rubin

unread,

Jul 1, 2009, 12:53:52 PM7/1/09

to Complexity Course, Spring 2009, Tel Aviv University

אומנם הרדוקציה באמת עוברת מ NAE3 ל B4SAT
אבל השאלה מבקשת למצוא קושי קירוב..
האם אנו יודעים משהו על קושי הקירוב של 3NAE ? כי בלי לדעת משהו על קושי
הקירוב של זה או בעיית GAP שהיא NP-קשה,
אני לא רואה דרך להראות שאכן קיים C כזה בהינתן הרדוקציה

On 1 יולי, 17:16, yuval rochman <yuval...@gmail.com> wrote:
> רדוקציה מNAE3-SAT:
> לכל הסגר x1Vx2Vx3 נוסיף משתנה x4 ונקבל נוסחא x1Vx2Vx3Vx4.
>

> 2009/7/1 Yossi <jozar...@gmail.com>

Yossi

unread,

Jul 1, 2009, 2:19:53 PM7/1/09

to Complexity Course, Spring 2009, Tel Aviv University

יודעים על קושי הקירוב של 3NAE
בשיעורי בית היה לנו רדוקציה מ 3SAT ל 3NAE שמכפילה את מספר הפסוקיות

Rotem

unread,

Jul 1, 2009, 4:15:18 PM7/1/09

to Complexity Course, Spring 2009, Tel Aviv University

עודד כתב פה אתמול שהרדוקציה היא לגאפ של [1, 15/16+eps]
לכן הקירוב הכי טוב הוא 16/15+eps

> > > > ג. הראו שקיים קבוע c>0 כך שלקרב את B4SAT טוב יותר מ-c זו בעיה NP-hard.-הסתר טקסט מצוטט-
>
> -הראה טקסט מצוטט-

Reply all

Reply to author

Forward