מפת הסיבוכיות
EN
קודקוד $N$ ששורף צבע, משולש לכל פסוקית

3NAE ≤p 3COL

3NAE≤p3COL\mathrm{3NAE}\le_p\mathrm{3COL}, ולכן 3COL\mathrm{3COL} היא NP-שלמה.

הבנייה

על נוסחת 3CNF φ\varphi מעל x1,…,xnx_1,\dots,x_n עם mm פסוקיות. הפלט הוא גרף בלבד — אין מספר, כי k=3k=3 הוא חלק מה-DNA של הבעיה.

  1. קודקודים. לכל ii קודקוד עבור xix_i וקודקוד עבור xi‾\overline{x_i} (קודקודי ליטרלים); קודקוד מיוחד נוסף NN; ולכל פסוקית CjC_j שלושה קודקודים נוספים, אחד לכל ליטרל שלה (קודקודי פסוקית). סך הכול 2n+1+3m2n+1+3m קודקודים.
  2. קשתות.
    • שחורות: NN לכל קודקודי הליטרלים — 2n2n קשתות.
    • כחולות: כל ליטרל לשלילתו — nn קשתות.
    • אדומות: לכל פסוקית, משולש על שלושת קודקודי הפסוקית, וכן קשת מכל קודקוד פסוקית לקודקוד הליטרל המתאים לו — 3+3=63+3=6 קשתות לפסוקית.
  3. החזר את GG.

האינטואיציה. בצביעה חוקית, בלי הגבלת הכלליות f(N)=1f(N)=1. מכיוון ש-NN מחובר לכל קודקודי הליטרלים, כל קודקוד ליטרל צבוע ב-22 או ב-33; ומכיוון ש-xix_i מחובר ל-xi‾\overline{x_i}, מכל זוג כזה בדיוק אחד צבוע ב-22 ובדיוק אחד ב-33. הצבעים {2,3}\{2,3\} מתפקדים בדיוק כמו {אמת,שקר}\{\text{אמת},\text{שקר}\}, והקודקוד NN "שורף" עבורנו את הצבע הראשון. המשולשים אוכפים את תנאי ה-NAE.

הבחנה שבלבלה את הכיתה: לכל פסוקית יש שלושה קודקודים משלה, שהם עצמים נפרדים מקודקודי הליטרלים. קודקוד פסוקית "מתאים" לליטרל רק במובן שקיימת ביניהם קשת אדומה.

המחשה

בנייה מודרכת

3NAE → צביעה ב-3 צבעים

שלב 1 מתוך 7
הקלט φ(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)
מ-3NAE לצביעה ב-3 צבעים: N, קודקודי ליטרלים ומשולשי פסוקיותקודקוד מיוחד N מחובר בקשתות שחורות לשישה קודקודי ליטרלים; קשתות כחולות מחברות כל ליטרל לשלילתו; לכל אחת משתי הפסוקיות משולש אדום משלה שקודקודיו מחוברים לליטרלים של אותה פסוקית.NN — שורף את צבע 1x¬xy¬yz¬zקודקודי ליטרלים — 2n = 61:x1:y1:z2:¬x2:y2:¬zC₁ = (x ∨ y ∨ z)C₂ = (¬x ∨ y ∨ ¬z)קודקודי פסוקית — 3m = 6

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

3NAE ∈ ⟹ 3COL ∈

נניח φ∈3NAE\varphi\in\mathrm{3NAE}, ותהי VV הצבה המספקת אותה במובן NAE. נבנה צביעה ff:

  1. f(N)=1f(N)=1.
  2. לכל ii: אם V(xi)=1V(x_i)=1 אז f(xi)=2f(x_i)=2 ו-f(xi‾)=3f(\overline{x_i})=3; אחרת f(xi)=3f(x_i)=3 ו-f(xi‾)=2f(\overline{x_i})=2. שקול לכלל האחיד f(ℓ)=2  ⟺  V(ℓ)=1,f(ℓ)=3  ⟺  V(ℓ)=0(∗)f(\ell)=2\iff V(\ell)=1,\qquad f(\ell)=3\iff V(\ell)=0\qquad(\ast)
  3. תהי CC פסוקית עם ליטרלים ℓ1,ℓ2,ℓ3\ell_1,\ell_2,\ell_3 וקודקודי פסוקית c1,c2,c3c_1,c_2,c_3 (כאשר ctc_t מחובר ל-ℓt\ell_t). מכיוון ש-VV מספקת את CC במובן NAE, קיים tt עם V(ℓt)=1V(\ell_t)=1 וקיים t′t' עם V(ℓt′)=0V(\ell_{t'})=0; נבחר אחד מכל סוג ונצבע f(ct)=3f(c_t)=3, f(ct′)=2f(c_{t'})=2, ו-f(ct′′)=1f(c_{t''})=1 לשלישי.

כעת נוודא שאף קשת אינה מונוכרומטית:

  • שחורות: f(N)=1f(N)=1 ולכל ליטרל f(ℓ)∈{2,3}f(\ell)\in\{2,3\}. ✓
  • כחולות: לפי שלב 2 אחד צבוע 22 והשני 33. ✓
  • משולש הפסוקית: שלושת הקודקודים קיבלו 3,2,13,2,1 — שלושה צבעים שונים. ✓
  • אדומות בין קודקוד פסוקית לליטרל שלו: f(ct)=3f(c_t)=3 ולפי (∗)(\ast) f(ℓt)=2f(\ell_t)=2; f(ct′)=2f(c_{t'})=2 ולפי (∗)(\ast) f(ℓt′)=3f(\ell_{t'})=3; ו-f(ct′′)=1f(c_{t''})=1 ואילו f(ℓt′′)∈{2,3}f(\ell_{t''})\in\{2,3\}. ✓ (הצבע 11 תמיד פנוי לקודקוד פסוקית, כי 11 ניתן רק ל-NN ו-NN אינו מחובר לקודקודי פסוקיות.)

לכן ff צביעה חוקית ב-3 צבעים, כלומר G∈3COLG\in\mathrm{3COL}.

3COL ∈ ⟹ 3NAE ∈

תהי ff צביעה חוקית של GG בשלושה צבעים. מכיוון שפרמוטציה על שמות הצבעים שומרת על חוקיות, בלי הגבלת הכלליות f(N)=1f(N)=1.

צעד 1. כל קודקוד ליטרל ℓ\ell מחובר ל-NN בקשת שחורה, ולכן f(ℓ)≠1f(\ell)\ne1, כלומר f(ℓ)∈{2,3}f(\ell)\in\{2,3\}.

צעד 2. לכל ii הקשת הכחולה xixi‾x_i\overline{x_i} מחייבת f(xi)≠f(xi‾)f(x_i)\ne f(\overline{x_i}). יחד עם צעד 1: בדיוק אחד מבין xi,xi‾x_i,\overline{x_i} צבוע 22 והשני 33.

צעד 3 (ההצבה). נגדיר V(xi)=1  ⟺  f(xi)=2V(x_i)=1\iff f(x_i)=2. מצעד 2 נובע שאז f(xi‾)=3f(\overline{x_i})=3, ולכן שוב מתקיים הכלל האחיד (∗)(\ast). ההגדרה עקבית ומוגדרת היטב לכל משתנה.

צעד 4 (כל פסוקית מסופקת במובן NAE). תהי CC פסוקית עם ליטרלים ℓ1,ℓ2,ℓ3\ell_1,\ell_2,\ell_3 וקודקודי פסוקית c1,c2,c3c_1,c_2,c_3. השלושה יוצרים משולש, ולכן בצביעה חוקית הם נושאים שלושה צבעים שונים: {f(c1),f(c2),f(c3)}={1,2,3}\{f(c_1),f(c_2),f(c_3)\}=\{1,2,3\}. בפרט:

  • קיים tt עם f(ct)=2f(c_t)=2. הקשת האדומה ctℓtc_t\ell_t מחייבת f(ℓt)≠2f(\ell_t)\ne2, ומצעד 1 נובע f(ℓt)=3f(\ell_t)=3, ולכן לפי (∗)(\ast) מתקיים V(ℓt)=0V(\ell_t)=0.
  • קיים ss עם f(cs)=3f(c_s)=3. הקשת האדומה csℓsc_s\ell_s מחייבת f(ℓs)≠3f(\ell_s)\ne3, ולכן f(ℓs)=2f(\ell_s)=2, ולכן V(ℓs)=1V(\ell_s)=1.

ו-t≠st\ne s כי הצבעים שונים, ולכן ℓt≠ℓs\ell_t\ne\ell_s הם שני ליטרלים שונים של CC — כאן נכנסת ההנחה שבכל פסוקית שלושה ליטרלים שונים.

קיבלנו ב-CC ליטרל שההצבה נותנת לו 11 וליטרל שהיא נותנת לו 00, כלומר VV מספקת את CC במובן NAE. מכיוון ש-CC שרירותית, φ∈3NAE\varphi\in\mathrm{3NAE}.

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

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

קודקודים: 2n+1+3m2n+1+3m, ומכיוון ש-n,m≤∣φ∣n,m\le|\varphi| זה O(∣φ∣)O(|\varphi|). קשתות: 2n2n שחורות, nn כחולות, ובדיוק שש אדומות לכל פסוקית — 6m6m. סך הכול ∣V∣+∣E∣=O(∣φ∣)|V|+|E|=O(|\varphi|), כלומר זמן ליניארי.

מה זה קונה

3COL\mathrm{3COL} היא NP-קשה, וגם ב-NP\mathrm{NP} (העד הוא הצביעה, והמאמת עובר על הקשתות), ולכן NP-שלמה. משם מגיעה גם 4COL\mathrm{4COL} דרך 3COL≤p4COL\mathrm{3COL}\le_p\mathrm{4COL}.

מלכודות

  • אי אפשר לצבוע "את כל ה-xix_i ב-2 ואת כל ה-xi‾\overline{x_i} ב-3". הצביעה חייבת להיות תלויה בהצבה, אחרת שני ליטרלים שההצבה נתנה להם ערכים שונים היו מקבלים אותו צבע והקשר בין צבע לערך אמת נשבר.

  • כל משולש פסוקית נצבע בנפרד לחלוטין, בלי להתחשב בפסוקיות אחרות — בדיוק כמו שברדוקציה ל-MAXCUT\mathrm{MAXCUT} כל פסוקית תרמה קשתות משלה.

השרשרת

נשענת על

משמשת בהמשך ל

מאיפה זה נקרא

  • שיעור 10משפט 6: 3NAE≤p3COL\mathrm{3NAE} \le_p \mathrm{3COL}, ולכן 3COL\mathrm{3COL} היא NP-שלמה

  • כיוון ⟸\Longleftarrow הושאר בשיעור כתרגיל בית ורק שורטט בדקה האחרונה של ההקלטה; ההוכחה המלאה בקובץ השיעור היא השלמה לפי הסקיצה של המרצה.