3SAT ≤p IS | Complexity Atlas

הבנייה

על נוסחת 3CNF $\varphi$ עם $m$ פסוקיות:

קודקודים. לכל פסוקית $C_j$ נגדיר קודקוד עבור כל השמה חלקית המספקת אותה. פסוקית בת שלושה ליטרלים מעל שלושה משתנים שונים מסופקת על ידי $7$ מתוך $8$ ההשמות החלקיות, ולכן תורמת $7$ קודקודים.
קשתות. נחבר בקשת כל שני קודקודים שההשמות החלקיות שלהם סותרות זו את זו — כלומר קיים משתנה שאחת נותנת לו $\mathrm{True}$ והשנייה $\mathrm{False}$ . בפרט כל שני קודקודים של אותה פסוקית מחוברים, שכן שתי השמות מספקות שונות של אותה פסוקית נבדלות בערך של משתנה כלשהו; כלומר קודקודי כל פסוקית יוצרים קליקה.
החזר $\langle G,m\rangle$ .

האינטואיציה: קבוצה בלתי תלויה בגודל $m$ חייבת לבחור בדיוק קודקוד אחד מכל פסוקית (כי כל פסוקית היא קליקה), והיעדר קשתות בין הנבחרים אומר בדיוק שההשמות החלקיות שנבחרו עקביות זו עם זו — ולכן מתלכדות להשמה אחת המספקת את כל הפסוקיות.

המחשה

φ =(x ∨ y ∨ z)∧(¬x ∨ y ∨ w)∧(¬y ∨ z ∨ w)

קשת באותה פסוקיתסתירה בין משלימים

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

3SAT ∈ ⟹ IS ∈

נניח $\varphi\in\mathrm{3SAT}$ , ותהי $v$ השמה מספקת. לכל פסוקית $C_j$ , הצמצום של $v$ למשתני $C_j$ הוא השמה חלקית המספקת את $C_j$ , ולכן קיים בגרף קודקוד $u_j$ המתאים לה. נגדיר $U=\{u_1,\dots,u_m\}$ .

$|U|=m$ : הקודקודים שייכים לפסוקיות שונות ולכן הם עצמים שונים.

$U$ בלתי תלויה: יהיו $u_j,u_{j'}\in U$ שונים. שתי ההשמות החלקיות הן צמצומים של אותה השמה $v$ , ולכן לכל משתנה המופיע בשתיהן הן נותנות את אותו ערך — הן אינן סותרות. לפי הבנייה קשת קיימת רק בין השמות סותרות, ולכן $u_ju_{j'}\notin E$ .

לכן $\langle G,m\rangle\in\mathrm{IS}$ .

IS ∈ ⟹ 3SAT ∈

נניח $\langle G,m\rangle\in\mathrm{IS}$ , ותהי $U$ קבוצה בלתי תלויה בגודל $m$ .

צעד 1 — בדיוק קודקוד אחד לכל פסוקית. קודקודי כל פסוקית יוצרים קליקה, ולכן $U$ מכילה לכל היותר קודקוד אחד מכל פסוקית. יש $m$ פסוקיות ו- $|U|=m$ , ולכן $U$ מכילה בדיוק אחד מכל פסוקית. נסמן אותו $u_j$ , ואת ההשמה החלקית שלו $\sigma_j$ .

צעד 2 — ההשמות עקביות. לכל $j\ne j'$ הקודקודים $u_j,u_{j'}$ אינם מחוברים (כי $U$ בלתי תלויה), ולכן לפי הבנייה $\sigma_j$ ו- $\sigma_{j'}$ אינן סותרות: כל משתנה המופיע בשתיהן מקבל בהן אותו ערך.

צעד 3 — הרכבת ההשמה. נגדיר השמה מלאה $v$ : אם משתנה $x$ מופיע באיזשהו $\sigma_j$ , נקבע $v(x)=\sigma_j(x)$ — לפי צעד 2 ההגדרה אינה תלויה בבחירת $j$ ולכן מוגדרת היטב; אם $x$ אינו מופיע באף $\sigma_j$ , נקבע $v(x)=0$ שרירותית.

צעד 4 — $v$ מספקת. תהי $C_j$ פסוקית. ההשמה $\sigma_j$ מספקת אותה לפי הבנייה, ו- $v$ מסכימה עם $\sigma_j$ על כל משתני $C_j$ , ולכן $v$ מספקת את $C_j$ . מכיוון ש- $j$ שרירותי, $v$ מספקת את $\varphi$ , כלומר $\varphi\in\mathrm{3SAT}$ .

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

זמןO(|φ|²)

מקוםO(|φ|²)

גודל הפלטO(m²) vertices-pairs, O(m) vertices

הנקודה הקריטית: החסם $7$ לקודקודים לפסוקית תקף רק מפני שאורך הפסוקית חסום. לנוסחת CNF כללית מספר ההשמות המספקות פסוקית באורך $k$ הוא $2^k-1$ — מעריכי, והבנייה לא הייתה פולינומית. זו הסיבה שמתחילים מ- $\mathrm{3SAT}$ ולא מ- $\mathrm{SAT}$ .

מה זה קונה

$\mathrm{IS}$ היא NP-שלמה, ומכאן — דרך $\mathrm{IS}\le_p\mathrm{CLIQUE}$ ו- $\mathrm{IS}\le_p\mathrm{VC}$ — גם $\mathrm{CLIQUE}$ ו- $\mathrm{VC}$ .

מלכודות

הסף המוחזר הוא $m$ — מספר הפסוקיות, לא מספר המשתנים ולא מספר הקודקודים. הסף הזה הוא שכופה "אחד מכל פסוקית", ובלעדיו צעד 1 של הכיוון השני קורס.
הקשתות בתוך פסוקית אינן "תוספת" — הן נובעות מאותו כלל בדיוק (השמות סותרות), שכן שתי השמות מספקות שונות של אותה פסוקית חייבות להיבדל במשתנה כלשהו. אפשר לנסח את הבנייה בכלל אחד ולא בשניים.

השרשרת

נשענת על

SAT ≤p 3SAT

משמשת בהמשך ל

IS ≤p VC

מאיפה זה נקרא

תרגיל מודרךsat-to-independent-set
2024 '1 מועד 1ספירת הקשתות בפלט הרדוקציה על $(x_1\vee x_2\vee x_3)\wedge(x_1\vee x_4)$ .
2024 '1 מועד 2אותה בנייה, ספירה על נוסחה אחרת.
2025"הוכיחו את נכונות הבנייה ונתחו את זמן הריצה. האם זמן הריצה פולינומי?"

הבנייה הזאת אינה מופיעה בשיעורי 2026ב׳ — שם $\mathrm{IS}$ מוצגת בשיעור 7 והקושי שלה מגיע בהמשך דרך מסלול אחר. היא מתועדת כאן לפי הניסוח שהבחינות עצמן נותנות לה (2024 ו-2025 מתארות אותה במפורש כ"הרדוקציה שראינו"), ולכן היא ממופה למקורות הבחינה ולתרגיל המודרך ולא לשיעור.