מפת הסיבוכיות
EN
ליטרל רביעי משותף

3SAT ≤p 4NAE

3SAT≤p4NAE\mathrm{3SAT}\le_p\mathrm{4NAE}, ולכן 4NAE\mathrm{4NAE} היא NP-קשה. נוסחה ספיקה במובן NAE אם קיימת השמה שבה בכל פסוקית יש ליטרל שערכו אמת וליטרל שערכו שקר.

הבנייה

על נוסחת 3CNF φ\varphi עם פסוקיות C1,…,CmC_1,\dots,C_m, כאשר Cj=ℓj,1∨ℓj,2∨ℓj,3C_j=\ell_{j,1}\vee\ell_{j,2}\vee\ell_{j,3}:

  1. נבחר משתנה חדש יחיד zz, משותף לכל הפסוקיות.
  2. לכל jj נגדיר את הפסוקית בת ארבעת הליטרלים Cj′=ℓj,1∨ℓj,2∨ℓj,3∨z.C_j'=\ell_{j,1}\vee\ell_{j,2}\vee\ell_{j,3}\vee z .
  3. החזר את φ′=⋀j=1mCj′\varphi'=\bigwedge_{j=1}^{m}C_j'.

האינטואיציה: המשתנה zz משמש כ"קרקע" משותפת. אם נקבע z=0z=0, אז הדרישה "קיים ליטרל שקר" מסופקת אוטומטית בכל פסוקית, ונשארת רק הדרישה "קיים ליטרל אמת" — כלומר בדיוק ספיקות רגילה.

המחשה

בנייה מודרכת

3SAT → 4NAE

שלב 1 מתוך 7
φ = (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) ∧ (x₁ ∨ ¬x₂ ∨ ¬x₃)
מ-3SAT ל-4NAE: טבלת פסוקיות עם הליטרל z שנוסףכל שורה היא פסוקית וכל תא הוא ליטרל, צבוע לפי ערכו תחת ההשמה הנוכחית. העמודה הרביעית מחזיקה את הליטרל החדש המשותף z. תוויות ההכרעה מימין אומרות אם הפסוקית מסופקת ואם היא מסופקת במובן NAE.φ תחת v = (1,1,1) — מסופקת, אבל פסוקית 1 כולה אמתC₁x₁ = 1x₂ = 1x₃ = 1מסופקת ✓כולם שווים ✗C₂¬x₁ = 0x₂ = 1¬x₃ = 0מסופקת ✓NAE ✓C₃x₁ = 1¬x₂ = 0¬x₃ = 0מסופקת ✓NAE ✓x₁ = 1x₂ = 1x₃ = 1
ערך הליטרל 1ערך הליטרל 0

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

3SAT ∈ ⟹ 4NAE ∈

נניח ש-φ\varphi ספיקה על ידי vv. נרחיב את vv על ידי v(z)=0v(z)=0 ונראה שהיא מספקת את φ′\varphi' במובן NAE.

תהי Cj′C_j' פסוקית של הפלט. מכיוון ש-vv מספקת את CjC_j, קיים tt עם v(ℓj,t)=1v(\ell_{j,t})=1 — הרי לנו ליטרל אמת ב-Cj′C_j'. ומכיוון ש-v(z)=0v(z)=0, הליטרל zz עצמו הוא ליטרל שקר ב-Cj′C_j'. לכן Cj′C_j' מסופקת במובן NAE. מכאן φ′∈4NAE\varphi'\in\mathrm{4NAE}.

4NAE ∈ ⟹ 3SAT ∈

נניח φ′∈4NAE\varphi'\in\mathrm{4NAE}, ותהי vv השמה המספקת אותה במובן NAE. נשתמש בסימטריה המרכזית של NAE: אם vv מספקת נוסחה במובן NAE, אז גם ההשמה המשלימה vˉ\bar v מספקת אותה במובן NAE — כי היפוך כל הערכים מחליף בין הליטרל האמת לליטרל השקר בכל פסוקית, ושניהם עדיין קיימים.

לכן, בלי הגבלת הכלליות, v(z)=0v(z)=0 (אחרת נעבור ל-vˉ\bar v). נצמצם כעת את vv למשתני φ\varphi. תהי CjC_j פסוקית של φ\varphi. הפסוקית Cj′C_j' מסופקת במובן NAE, ולכן קיים בה ליטרל שערכו 11. הליטרל zz אינו יכול להיות הליטרל הזה, שכן v(z)=0v(z)=0. לכן קיים tt עם v(ℓj,t)=1v(\ell_{j,t})=1, כלומר CjC_j מסופקת. מכאן φ\varphi ספיקה.

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

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

מעבר יחיד על הפסוקיות, בתוספת ליטרל אחד לכל פסוקית — mm ליטרלים נוספים ומשתנה חדש יחיד.

מה זה קונה

4NAE\mathrm{4NAE} היא NP-קשה. יחד עם 4NAE≤p3NAE\mathrm{4NAE}\le_p\mathrm{3NAE} ועם הטרנזיטיביות מתקבל 3SAT≤p3NAE\mathrm{3SAT}\le_p\mathrm{3NAE}, ומכאן ש-3NAE\mathrm{3NAE} היא נקודת מוצא קשה לשתי הרדוקציות של שיעור 10.

מלכודות

  • המשתנה zz הוא אחד לכל הנוסחה, לא אחד לכל פסוקית. אילו הקצינו zjz_j נפרד לכל פסוקית, כיוון ⇐\Leftarrow עדיין היה עובד, אבל טיעון הסימטריה "בלי הגבלת הכלליות z=0z=0" היה מאבד את כוחו — היפוך גלובלי אינו יכול לקבע mm משתנים שונים בו-זמנית לערך הרצוי.

  • סימטריית ההשלמה היא תכונה של NAE בלבד. בספיקות רגילה היא אינה נכונה, ולכן אי אפשר להעתיק את הטיעון הזה לרדוקציות שאינן NAE.

השרשרת

נשענת על

משמשת בהמשך ל

מאיפה זה נקרא

  • שיעור 10משפט 3: 3NAE\mathrm{3NAE} ו-4NAE\mathrm{4NAE} הן NP-קשות
  • 2024הגדרת kNAEk\mathrm{NAE} והוכחת קשיות דרך משפחת ה-NAE.

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