מפת הסיבוכיות
EN
קליקת פסוקית, קשת ליטרל–שלילה, סף $m$

SAT ≤p MaxIS

SAT≤pMaxIS\mathrm{SAT}\le_p\mathrm{MaxIS}, ולכן MaxIS\mathrm{MaxIS} היא NP-קשה. כאן MaxIS\mathrm{MaxIS} היא השפה של הזוגות ⟨G,k⟩\langle G,k\rangle שעבורם גודל הקבוצה הבלתי תלויה המקסימלית הוא בדיוק kk.

הבנייה

על נוסחת CNF כללית φ\varphi עם mm פסוקיות — לא בהכרח 3CNF; פסוקית יכולה להיות מכל גודל. נבנה את Gφ=(V,E)G_\varphi=(V,E):

  1. קודקודים. לכל פסוקית, ולכל ליטרל בפסוקית — קודקוד. ליטרל שמופיע בכמה פסוקיות מקבל כמה קודקודים, אחד לכל מופע: הקודקוד מייצג מופע, לא משתנה.
  2. קשתות אדומות (בתוך פסוקית). לכל פסוקית, קשת בין כל שני קודקודים שנוצרו ממנה — כל פסוקית הופכת לקליקה.
  3. קשתות שחורות (ליטרל ושלילתו). קשת בין כל קודקוד של ליטרל לכל קודקוד של שלילתו.
  4. החזר ⟨Gφ,m⟩\langle G_\varphi,m\rangle.

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

המחשה

בנייה מודרכת

SAT → MaxIS

שלב 1 מתוך 7
φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃)m = 3 פסוקיות
הגרף G_φ הנבנה מנוסחת CNF בת שלוש פסוקיותשבעה קודקודים מסודרים בשלושה טורי פסוקיות. קשתות אדומות מלאות הופכות כל פסוקית לקליקה; קשתות כהות מקווקוות מחברות כל ליטרל לשלילתו. שלושה קודקודים נבחרים, אחד מכל פסוקית, מרכיבים קבוצה בלתי תלויה בגודל שלוש.G_φ — קודקוד לכל מופע ליטרלC₁ = (x₁ ∨ ¬x₂)C₂ = (¬x₁ ∨ x₂ ∨ x₃)C₃ = (¬x₂ ∨ ¬x₃)x₁¬x₂¬x₁x₂x₃¬x₂¬x₃¬x₂ מופיע פעמיים ← שני קודקודים
קודקוד = מופע ליטרל אחד

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

SAT ∈ ⟹ MaxIS ∈

נניח φ∈SAT\varphi\in\mathrm{SAT}; קיימת השמה V\mathcal V המספקת אותה, כלומר לכל פסוקית קיים לפחות ליטרל אחד שערכו 11. (סדר הכמתים חשוב: לא "קיים ליטרל לכל פסוקית", שהיא טענה חזקה בהרבה ופשוט לא נכונה.)

נסמן ב-UU קבוצה המורכבת מקודקוד אחד כזה מכל פסוקית. מכיוון שיש mm פסוקיות וקודקודים של פסוקיות שונות שונים זה מזה, ∣U∣=m|U|=m.

UU בלתי תלויה. יהיו x,y∈Ux,y\in U שונים.

  • קשת אדומה? ב-UU יש בדיוק קודקוד אחד לכל פסוקית, ולכן x,yx,y נוצרו מפסוקיות שונות; קשת אדומה מחברת רק קודקודים מאותה פסוקית.
  • קשת שחורה? לפי הבחירה, V\mathcal V נותנת לשני הליטרלים המתאימים את הערך 11. אבל ליטרל ושלילתו לעולם אינם מקבלים שניהם 11, ולכן x,yx,y אינם ליטרל ושלילתו.

עדיין לא סיימנו — זה רק חלק ה"קיים". צריך גם את חלק ה"לכל":

טענה (חסם המקסימליות): כל קבוצה בלתי תלויה ב-GφG_\varphi היא בגודל ≤m\le m. תהא U^\hat U בלתי תלויה. כל שני קודקודים של אותה פסוקית מחוברים בקשת אדומה, ולכן אין ב-U^\hat U שניים מאותה פסוקית; יש mm פסוקיות, ולכן ∣U^∣≤m|\hat U|\le m. שימו לב שהטענה נכונה לכל φ\varphi, גם לא ספיקה — היא תלויה אך ורק בקשתות האדומות.

שילוב השניים: קיימת בלתי תלויה בגודל mm, וכל בלתי תלויה היא בגודל ≤m\le m. לכן α(Gφ)=m\alpha(G_\varphi)=m, כלומר ⟨Gφ,m⟩∈MaxIS\langle G_\varphi,m\rangle\in\mathrm{MaxIS}.

MaxIS ∈ ⟹ SAT ∈

נניח ⟨Gφ,m⟩∈MaxIS\langle G_\varphi,m\rangle\in\mathrm{MaxIS}, כלומר α(Gφ)=m\alpha(G_\varphi)=m; אזי קיימת UU בלתי תלויה עם ∣U∣=m|U|=m.

  1. UU בלתי תלויה, ולכן בין כל שני קודקודים בה אין קשת אדומה; מכאן ש-UU מכילה לכל היותר קודקוד אחד מכל פסוקית.
  2. מכיוון ש-∣U∣=m|U|=m ויש בדיוק mm פסוקיות, ולכל פסוקית לכל היותר אחד — לפי שובך יונים (בכיוון הצפוף) UU מכילה בדיוק קודקוד אחד מכל פסוקית.

(אלה שני טיעונים נפרדים: הראשון מגיע מאי-התלות, השני מספירה.)

  1. UU בלתי תלויה, ולכן אין בין קודקודיה קשת שחורה; לכן אין ב-UU שני קודקודים המתאימים לליטרל ולשלילתו.
  2. אוסף הליטרלים המתאימים לקודקודי UU הוא אפוא עקבי: אין בו משתנה המופיע גם חיובי וגם שלילי. לכן קיימת השמה V\mathcal V המספקת את כל הליטרלים האלה — לכל משתנה שמופיע באוסף נותנים את הערך שמספק את מופעו, ולשאר המשתנים ערך שרירותי.
  3. לפי סעיף 2 ב-UU יש קודקוד מכל פסוקית, ולכן V\mathcal V מספקת לפחות ליטרל אחד בכל פסוקית, כלומר מספקת את φ\varphi.

מכאן φ∈SAT\varphi\in\mathrm{SAT}.

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

זמןO(|φ|²)
מקוםO(|φ|²)
גודל הפלט|V| ≤ |φ|, |E| = O(|φ|²)

יצירת הקודקודים היא מעבר יחיד על הנוסחה, O(∣φ∣)O(|\varphi|), ובפרט ∣V∣≤∣φ∣|V|\le|\varphi| — כל קודקוד נולד ממופע ליטרל אחד. הקשתות דורשות מעבר על כל הזוגות, (∣V∣2)=O(∣V∣2)=O(∣φ∣2)\binom{|V|}{2}=O(|V|^2)=O(|\varphi|^2), כשההחלטה לכל זוג היא בדיקה מקומית בזמן קבוע. סך הכול O(∣φ∣2)O(|\varphi|^2).

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

מה זה קונה

MaxIS\mathrm{MaxIS} היא NP-קשה. יחד עם IS‾≤pMaxIS\overline{\mathrm{IS}}\le_p\mathrm{MaxIS} היא גם coNP-קשה, ושתי התכונות יחד נותנות את התוצאה החריגה: MaxIS∈NP∪coNP\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP} אם ורק אם NP=coNP\mathrm{NP}=\mathrm{coNP}.

מלכודות

  • הכיוון הראשון דורש שתי טענות, לא אחת. ב-IS\mathrm{IS} די להראות שקיימת קבוצה בגודל mm; ב-MaxIS\mathrm{MaxIS} צריך גם שאין גדולה יותר. זה בדיוק המקום שבו תרגיל הבית על SAT≤pIS\mathrm{SAT}\le_p\mathrm{IS} מסתיים והעבודה כאן מתחילה.

  • טענת "לכל" מתחילה ב"תהא". חסם המקסימליות הוא טענה על כל קבוצה בלתי תלויה, ולכן ההוכחה חייבת לפתוח ב"תהא U^\hat U בלתי תלויה" — רק אחרי שהמשתנה הוצג אפשר להניח בשלילה.

  • "קיימת השמה", לא "ניתן לקבוע את ההשמה". אין כאן יחידות: משתנה שאינו מופיע ב-UU כלל מקבל ערך חופשי, ולכן יש כמה השמות מתאימות. ההוכחה גם מפסיקה בשלב הזה להיות אלגוריתמית — היא מוכיחה קיום גורר קיום, וטיעון אלגוריתמי הוא רק דרך אחת לעשות זאת.

השרשרת

נשענת על

משמשת בהמשך ל

מאיפה זה נקרא

  • שיעור 22משפט 2: SAT≤pMaxIS\mathrm{SAT}\le_p\mathrm{MaxIS}, ולכן MaxIS\mathrm{MaxIS} היא NP-קשה
  • 2025"נגדיר את MAX-ISMAX\text{-}IS כבעיית ההכרעה שבה נשאל אם גודל הקבוצה הבלתי תלויה המקסימלית הוא בדיוק kk. הוכיחו כי MAX-ISMAX\text{-}IS היא NPNP-קשה."