רדוקציה מ־NAE-3SAT ל־Max-Cut במולטי־גרף

בניית קשתות משתנים ופסוקיות כך שחתך בגודל n+2m מקודד השמת not-all-equal.

שאלה

תהא NAE-3SAT שפת נוסחאות 3CNF שיש להן השמה שבה בכל פסוקית יש ליטרל אמיתי וליטרל שקרי. Max-Cut-Multi מקבלת מולטי־גרף $G$ ומספר $K$ ושואלת אם קיים חתך עם לפחות $K$ קשתות חוצות (עם ריבוי).

בהינתן נוסחת 3CNF $\varphi$ עם $n$ משתנים ו-$m$ פסוקיות (בכל פסוקית שלושה משתנים שונים), בנו מולטי־גרף $G$ וסף $K=n+2m$ כך ש-$\varphi\in\mathrm{NAE\text{-}3SAT}$ אם ורק אם $(G,K)$ מופע־כן. הוכיחו את שני הכיוונים ואת הגודל הפולינומי.

רמז 1

הקודקודים ייצגו ליטרלים $x_i$ ו-$\neg x_i$.

רמז 2

תגמלו חיתוך כל זוג משתנים פעם אחת, וחיתוך שתיים משלוש קשתות בכל משולש פסוקית.

פתרון מלא

יוצרים קודקודים $\{x_1,\neg x_1,\ldots,x_n,\neg x_n\}$. מוסיפים קשת $\{x_i,\neg x_i\}$ לכל משתנה. לכל פסוקית $(\ell_a\lor\ell_b\lor\ell_c)$ מוסיפים שלוש קשתות הפסוקית, כולל מקבילות בעת חזרה. מחזירים $K=n+2m$.

חתך מגיע ל-$n+2m$ אם ורק אם כל זוג משלימים מופרד וכל פסוקית אינה חד־צדדית (תרומה $2$ למשולש). מכאן השקילות ל־NAE. הגודל פולינומי: $2n$ קודקודים ו-$n+3m$ קשתות לרישום.

נקודת ביקורת

קשתות המשתנים כופות עקביות; הניקוד $2$ לפסוקית כופה NAE ולא רק SAT.

טעויות נפוצות

• סף $n+3m$ או $n+m$ ששובר את האפיון ההדוק.
• שכחת קשתות מקבילות.
• השארת $x$ ו-$\neg x$ באותו צד ועדיין טענת גודל $K$.

הערת מקור

הצגה עצמאית של משפחת הרדוקציה מתרגיל 4 תשפ״ו (שאלה 2). הטקסט מקורי; המטלה מצוטטת כמקור לפרמטרי הבנייה, לא כפתרון מועתק.

מקורות ואימות

• Semester A 2026 exercise 4, Q2
• סיכומי Max-Cut בקורס
• מיפוי קטלוג: data/exercises.json; הניסוחים והפתרונות נכתבו באופן עצמאי.

פתיחה בגלריית ההמחשות: NAE-3SAT → Max-Cut