עמודת משתנה ועמודת פסוקית, עם ספרות ריפוד

3SAT ≤p SUBSET-SUM

$\mathrm{3SAT}\le_p\mathrm{SUBSET\text{-}SUM}$ — הגרסה הקלאסית של הרדוקציה, שבה בחירת ההשמה וסיפוק הפסוקיות מקודדים בעמודות ספרות ללא נשאות.

הבנייה

על נוסחת 3CNF $\varphi$ עם משתנים $x_1,\dots,x_n$ ופסוקיות $C_1,\dots,C_m$ . כל המספרים נכתבים בבסיס $10$ ובעלי $n+m$ ספרות: $n$ עמודות משתנה ואחריהן $m$ עמודות פסוקית.

שני מספרים לכל משתנה. לכל $i$ $i$ נגדיר $y_i$ $y_{i}$ (עבור $x_i=\mathrm{True}$ $x_{i} = True$ ) ו- $z_i$ $z_{i}$ (עבור $x_i=\mathrm{False}$ $x_{i} = False$ ):
- בעמודת המשתנה $i$ — הספרה $1$ בשניהם; בכל עמודת משתנה אחרת — $0$ .
- בעמודת הפסוקית $j$ — ב- $y_i$ הספרה $1$ אם הליטרל $x_i$ מופיע ב- $C_j$ , אחרת $0$ ; ב- $z_i$ הספרה $1$ אם $\overline{x_i}$ מופיע ב- $C_j$ , אחרת $0$ .
שני מספרי ריפוד לכל פסוקית. לכל $j$ נגדיר $g_j$ ו- $h_j$ , שבשניהם הספרה $1$ בעמודת הפסוקית $j$ ו- $0$ בכל מקום אחר.
סכום היעד $S$ : הספרה $1$ בכל עמודת משתנה, והספרה $3$ בכל עמודת פסוקית.
החזר את כל המספרים ואת $S$ .

מה כל עמודה אוכפת. עמודת משתנה דורשת בדיוק $1$ , וכיוון שרק $y_i$ ו- $z_i$ נושאים שם $1$ — נבחר בדיוק אחד מהם, כלומר ההשמה מוגדרת היטב. עמודת פסוקית דורשת $3$ , ושני מספרי הריפוד יכולים לתרום לכל היותר $2$ ; לכן חייב להיבחר לפחות מספר משתנה אחד התורם לעמודה הזאת — כלומר הפסוקית מסופקת.

המחשה

φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂)

מספר

x₁

x₂

C₁

C₂

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

3SAT ∈ ⟹ SUBSET-SUM ∈

נניח ש- $v$ מספקת את $\varphi$ . נבחר את המספרים:

לכל $i$ : אם $v(x_i)=1$ נבחר את $y_i$ , אחרת את $z_i$ .
לכל $j$ : נסמן ב- $s_j\in\{1,2,3\}$ את מספר הליטרלים של $C_j$ שההשמה מספקת (לפחות $1$ , כי $v$ מספקת את $C_j$ , ולכל היותר $3$ ). נבחר $3-s_j$ ממספרי הריפוד של $C_j$ — כלומר $2,1$ או $0$ מהם. זה אפשרי כי $3-s_j\in\{0,1,2\}$ ויש שני מספרי ריפוד.

עמודות משתנה. בעמודה $i$ תרם בדיוק מספר אחד ( $y_i$ או $z_i$ ) את הספרה $1$ ; מספרי הריפוד תורמים $0$ שם, ומספרי משתנים אחרים תורמים $0$ בעמודה $i$ . הסכום הוא $1$ — כנדרש.

עמודות פסוקית. בעמודה $j$ תורמים מספרי המשתנים הנבחרים בדיוק $s_j$ (מספר הליטרלים המסופקים של $C_j$ ), ומספרי הריפוד הנבחרים תורמים $3-s_j$ . הסכום הוא $s_j+(3-s_j)=3$ — כנדרש.

הספרות המרביות בכל עמודה חסומות: בעמודת משתנה לכל היותר $2$ , ובעמודת פסוקית לכל היותר $3+2=5$ , ולכן אין נשאות ואפשר לקרוא ספרה-ספרה. הסכום הכולל הוא בדיוק $S$ .

SUBSET-SUM ∈ ⟹ 3SAT ∈

נניח שקיימת תת-קבוצה $I$ שסכומה $S$ . מכיוון שבכל עמודה סכום הספרות חסום ב- $5<10$ (בעמודת משתנה לכל היותר $2$ ; בעמודת פסוקית לכל היותר $3$ ממספרי משתנים ועוד $2$ מהריפוד), אין נשאות, ולכן שוויון הסכומים גורר שוויון בכל עמודה בנפרד.

עמודות משתנה. בעמודה $i$ נדרש סכום $1$ . רק $y_i$ ו- $z_i$ נושאים שם ספרה שאינה $0$ , ושניהם נושאים $1$ . לכן בדיוק אחד מהם ב- $I$ . נגדיר השמה: $v(x_i)=1$ אם $y_i\in I$ , ו- $v(x_i)=0$ אם $z_i\in I$ . ההגדרה מוגדרת היטב ומלאה.

עמודות פסוקית. בעמודה $j$ נדרש סכום $3$ . התורמים הם מספרי הריפוד $g_j,h_j$ — לכל היותר $2$ יחד — ומספרי משתנים שנבחרו והליטרל שלהם מופיע ב- $C_j$ . לכן מספרי המשתנים תורמים לפחות $3-2=1$ , כלומר קיים מספר משתנה נבחר התורם $1$ לעמודה $j$ .

יהי כזה מספר. אם הוא $y_i$ , אז לפי הבנייה הליטרל $x_i$ מופיע ב- $C_j$ , ולפי ההגדרה $v(x_i)=1$ — הליטרל מסופק. אם הוא $z_i$ , אז $\overline{x_i}$ מופיע ב- $C_j$ ו- $v(x_i)=0$ — שוב הליטרל מסופק. בשני המקרים $C_j$ מסופקת.

מכיוון ש- $j$ שרירותי, $v$ מספקת את $\varphi$ , כלומר $\varphi\in\mathrm{3SAT}$ .

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

זמןO((n+m)²)

מקוםO((n+m)²)

גודל הפלט(2n + 2m + 1) numbers of n+m digits each

מספר המספרים בפלט הוא $2n$ (שניים לכל משתנה) ועוד $2m$ (שניים לכל פסוקית), ולכל אחד $n+m$ ספרות. סך הספרות בפלט הוא אפוא $(2n+2m)(n+m)+(n+m)=O((n+m)^2)$ — זו בדיוק הספירה שהבחינות שאלו עליה. הזמן פרופורציוני לגודל הפלט.

כמו ב- $\mathrm{VC}\le_p\mathrm{SUBSET\text{-}SUM}$ : הערך של כל מספר מעריכי בגודל הקלט, ואילו אורך הכתיבה שלו פולינומי — וזה מה שהופך את הרדוקציה לחוקית.

מה זה קונה

$\mathrm{SUBSET\text{-}SUM}$ היא NP-קשה, בדרך שאינה עוברת דרך $\mathrm{VC}$ .

מלכודות

צריך שני מספרי ריפוד לפסוקית, לא אחד. פסוקית יכולה להיות מסופקת על ידי $1$ , $2$ או $3$ ליטרלים, ולכן הפער עד $3$ הוא $2,1$ או $0$ — ושני מספרי ריפוד הם בדיוק מה שמכסה את שלוש האפשרויות. עם מספר ריפוד אחד, פסוקית שמסופקת על ידי ליטרל יחיד לא הייתה מגיעה ל- $3$ .
הסף בעמודת פסוקית הוא $3$ ולא $1$ . לו היה $1$ , מספר הריפוד לבדו היה מספק את העמודה ללא שום מספר משתנה — והכיוון השני היה קורס.

השרשרת

נשענת על

SAT ≤p 3SAT

מאיפה זה נקרא

2025 '1 מועד 1"מה מספר הספרות הכולל בכל המספרים בפלט הרדוקציה על נוסחת 3CNF עם $n$ משתנים ו- $m$ פסוקיות?"
2024 '1 מועד 1"ראינו בכיתה רדוקציה מ-3-SAT ל-Subset Sum" — מעקב אחרי ההתאמה בין השמה מספקת לתת-קבוצה.
2024 '1 מועד 2אותה בנייה, על נוסחה קונקרטית.
2023 '2 מועד 2תיאור פונקציית הרדוקציה ל-Subset-Sum והאם היא חוקית.

מיפוי חשוב: שיעורי 2026ב׳ אינם מלמדים את הרדוקציה הזאת — שיעור 11 מוכיח את קשיות $\mathrm{SUBSET\text{-}SUM}$ דרך $\mathrm{VC}$ , בבנייה אחרת לגמרי (עמודה לכל קשת). הרדוקציה מ-3SAT היא זו שהבחינות של 2023–2025 מתייחסות אליה כ"ראינו בהרצאה", כלומר היא נלמדה בשנים קודמות. שתי הבניות נכונות ושתיהן בקורפוס, ואין לערבב ביניהן: הן נבדלות בקלט, בעמודות ובסף.
מכיוון שאין לרדוקציה הזאת מקור שיעור בקורפוס, פרטי הבנייה שלמעלה הם הצורה הסטנדרטית שמתיישבת עם הנתונים שהבחינות מוסרות (ספירת הספרות, ההתאמה השמה↔תת-קבוצה). ייתכנו הבדלי ניסוח קלים מול הצורה שנמסרה בכיתה באותן שנים.