מפת הסיבוכיות
EN
פיצול NAE במשתנה עזר

4NAE ≤p 3NAE

4NAE≤p3NAE\mathrm{4NAE}\le_p\mathrm{3NAE}, ולכן 3NAE\mathrm{3NAE} היא NP-קשה.

הבנייה

על נוסחת 4CNF φ\varphi, לכל פסוקית C=ℓ1∨ℓ2∨ℓ3∨ℓ4C=\ell_1\vee\ell_2\vee\ell_3\vee\ell_4 נקצה משתנה עזר חדש משלה zCz_C ונחליף אותה בזוג (ℓ1∨ℓ2∨zC)  ∧  (zˉC∨ℓ3∨ℓ4).(\ell_1\vee\ell_2\vee z_C)\;\wedge\;(\bar z_C\vee\ell_3\vee\ell_4).

החזר את הנוסחה המתקבלת. זהו בדיוק צעד הפיצול של SAT≤p3SAT\mathrm{SAT}\le_p\mathrm{3SAT} — אותה בנייה בדיוק — אלא שכאן יש להוכיח אותה מחדש תחת סמנטיקת NAE, שהיא דרישה חזקה יותר מספיקות רגילה.

המחשה

בנייה מודרכת

4NAE → 3NAE

שלב 1 מתוך 7
4NAE ברדוקציה ל‑3NAE על ידי פיצול כל פסוקיתשתי פסוקיות בנות ארבעה ליטרלים מפוצלות כל אחת לשתי פסוקיות בנות שלושה ליטרלים המחוברות במשתנה עזר ובשלילתו; ערכי הליטרלים מסומנים בעיגול עבור אמת ובריבוע עבור שקר, ואחריהם שלושת מקרי הכיוון הראשון וחילוץ ליטרל אמת וליטרל שקר בכיוון ההפוך.φ — 4CNF, בקריאת NAEC₁xℓ₁yℓ₂zℓ₃¬wℓ₄C₂¬xℓ₁wℓ₂zℓ₃yℓ₄כל פסוקית עומדת להתפצל לשתייםכל פסוקית עומדת להתפצל לשתיים

נכונות — שני הכיוונים

4NAE ∈ ⟹ 3NAE ∈

נניח ש-vv מספקת את φ\varphi במובן NAE. תהי C=ℓ1∨ℓ2∨ℓ3∨ℓ4C=\ell_1\vee\ell_2\vee\ell_3\vee\ell_4 פסוקית; אז תחת vv יש ב-CC ליטרל אמת וליטרל שקר. נקבע את zCz_C כך:

  • אם v(ℓ1)≠v(ℓ2)v(\ell_1)\ne v(\ell_2) — לזוג הראשון כבר יש אמת ושקר, ואז נקבע zCz_C כך שיסדר את הזוג השני: אם v(ℓ3)=v(ℓ4)v(\ell_3)=v(\ell_4) נקבע v(zC)=v(ℓ3)v(z_C)=v(\ell_3), ואז zˉC\bar z_C נותן את הערך ההפוך ב-(zˉC∨ℓ3∨ℓ4)(\bar z_C\vee\ell_3\vee\ell_4); אחרת כל בחירה מתאימה.
  • אם v(ℓ1)=v(ℓ2)=:bv(\ell_1)=v(\ell_2)=:b — מכיוון של-CC יש גם אמת וגם שקר, בהכרח קיים t∈{3,4}t\in\{3,4\} עם v(ℓt)=¬bv(\ell_t)=\lnot b. נקבע v(zC)=¬bv(z_C)=\lnot b. אז בפסוקית הראשונה ℓ1,ℓ2\ell_1,\ell_2 נותנים bb ו-zCz_C נותן ¬b\lnot b — אמת ושקר; ובפסוקית השנייה zˉC\bar z_C נותן bb ו-ℓt\ell_t נותן ¬b\lnot b — שוב אמת ושקר.

בכל המקרים שתי הפסוקיות מסופקות במובן NAE, ו-zCz_C אינו מופיע בשום פסוקית אחרת. לכן הפלט מסופק במובן NAE.

3NAE ∈ ⟹ 4NAE ∈

נניח ש-vv מספקת את הפלט במובן NAE, ונצמצם אותה למשתני φ\varphi. תהי C=ℓ1∨ℓ2∨ℓ3∨ℓ4C=\ell_1\vee\ell_2\vee\ell_3\vee\ell_4; נראה שיש בה גם אמת וגם שקר.

נסמן c=v(zC)c=v(z_C). הפסוקית (ℓ1∨ℓ2∨zC)(\ell_1\vee\ell_2\vee z_C) מסופקת במובן NAE, ולכן קיים בה ליטרל בערך ¬c\lnot c — וליטרל כזה חייב להיות ℓ1\ell_1 או ℓ2\ell_2 (שכן הליטרל השלישי הוא zCz_C שערכו cc). כלומר קיים s∈{1,2}s\in\{1,2\} עם v(ℓs)=¬cv(\ell_s)=\lnot c.

באותו אופן, הפסוקית (zˉC∨ℓ3∨ℓ4)(\bar z_C\vee\ell_3\vee\ell_4) מסופקת במובן NAE, והליטרל zˉC\bar z_C מקבל ¬c\lnot c; לכן קיים בה ליטרל בערך cc, והוא חייב להיות ℓ3\ell_3 או ℓ4\ell_4. כלומר קיים t∈{3,4}t\in\{3,4\} עם v(ℓt)=cv(\ell_t)=c.

קיבלנו ב-CC שני ליטרלים בערכים ¬c\lnot c ו-cc — כלומר אמת ושקר. לכן CC מסופקת במובן NAE, ומכיוון ש-CC שרירותית, φ∈4NAE\varphi\in\mathrm{4NAE}.

סיבוכיות הרדוקציה

זמןO(|φ|)
מקוםO(|φ|)
גודל הפלטO(|φ|)

כל פסוקית מטופלת פעם אחת: mm פסוקיות הופכות ל-2m2m, ונוספים mm משתנים חדשים. בניגוד ל-SAT≤p3SAT\mathrm{SAT}\le_p\mathrm{3SAT}, כאן אין לולאה — אורך הפסוקית הוא 44 קבוע, ולכן די בפיצול אחד.

מה זה קונה

3NAE\mathrm{3NAE} היא NP-קשה, ומכאן שהיא נקודת מוצא חוקית לרדוקציות 3NAE≤pMAXCUT\mathrm{3NAE}\le_p\mathrm{MAXCUT} ו-3NAE≤p3COL\mathrm{3NAE}\le_p\mathrm{3COL}.

מלכודות

  • אי אפשר להסתפק ב"זו אותה בנייה כמו ב-SAT≤p3SAT\mathrm{SAT}\le_p\mathrm{3SAT}, ולכן היא נכונה". סמנטיקת NAE שונה, וההוכחה שלמעלה משתמשת ב-zˉC\bar z_C בצורה שונה לגמרי — שם היא סיפקה פסוקית, כאן היא אוכפת ערך הפוך.

השרשרת

נשענת על

משמשת בהמשך ל

מאיפה זה נקרא

  • שיעור 10משפט 3: 3NAE\mathrm{3NAE} ו-4NAE\mathrm{4NAE} הן NP-קשות
  • 2024 '1 מועד 2"באחד מהתרגילים בקורס תוארה רדוקציה מהשפה 4-NAE לשפה 3-NAE" — ספירת הפלט.
  • 2024משפחת kNAEk\mathrm{NAE} והרדוקציות בתוכה.

  • כמו ב-3SAT≤p4NAE\mathrm{3SAT}\le_p\mathrm{4NAE}: השיעור מוסר את הרדוקציה כתרגיל בית ואינו כותב את הבנייה. הבחינה מ-2024 מאשרת שהיא אכן ניתנה בתרגיל בקורס, ולכן היא מסומנת כמקורית לקורפוס; הכתיבה המלאה כאן היא השלמה.