רדוקציות ושלמות

רדוקציות many-one פולינומיאליות והלוגיקה של הוכחות קושי ושלמות.

מטרות

• לבנות רדוקציות many-one פולינומיאליות, כולל כיוון, כוליות וניתוח קידוד.
• להשתמש בטרנזיטיביות ובסגירות כדי להעביר אלגוריתמים ושייכות למחלקות.
• להבדיל בין NP-קושי ל-NP-שלמות ולהסיק נכון את תוצאת P=NP.
• להבין את Cook–Levin כבניית טבלת חישוב פולינומיאלית מפורשת.
• להוכיח את שני כיווני הרדוקציה $\mathrm{3SAT}\le_m^p\mathrm{IS}$.

1. רדוקציה כמהדר מופעים

$A\le_m^pB$ אם קיימת פונקציה כוללת $f$, הניתנת לחישוב בזמן פולינומיאלי, כך שלכל מחרוזת

אם $D_B$ מכריע את $B$, אז $D_B(f(x))$ מכריע את $A$. לכן להוכחת קושי החץ הוא

הפחתת היעד אל המקור אינה מוכיחה שהיעד קשה. השקילות משמרת גם מופעי כן וגם מופעי לא.

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

2. טרנזיטיביות וסגירות

אם $A\le_m^pB$ באמצעות $f$ ו-$B\le_m^pC$ באמצעות $g$, אז $h=g\circ f$ מקיימת

אם זמני הריצה הם $p(n),q(m)$, אז $|f(x)|\le p(|x|)$ עד כדי קבוע, ולכן

שהוא פולינומי.

סגירות כלפי מטה. אם $A\le_m^pB$ ו-$B\in\mathrm P$, אז $A\in\mathrm P$. כך גם עבור NP ו-coNP.

עבור NP מחשבים $f(x)$ ומפעילים את המוודא של $B$. אורך התעודה נשאר פולינומיאלי כי $|f(x)|$ פולינומיאלי. עבור coNP משתמשים באותה פונקציה, שכן

3. קושי, שלמות ותוצאת P=NP

$B$ היא NP-קשה אם לכל $A\in\mathrm{NP}$ מתקיים $A\le_m^pB$. היא NP-שלמה אם בנוסף $B\in\mathrm{NP}$. הוכחת השייכות היא בדרך כלל מוודא; הקושי מתקבל מרדוקציה מבעיה NP-שלמה ידועה. שפה NP-קשה אינה חייבת להיות ב-NP ואף אינה חייבת להיות כריעה.

משפט. אם שפה NP-שלמה $B$ נמצאת ב-P, אז $\mathrm P=\mathrm{NP}$.

לכל $A\in\mathrm{NP}$ יש רדוקציה אל $B$. אלגוריתם פולינומיאלי ל-$B$ יחד עם הרדוקציה מכריע את $A$ בזמן פולינומיאלי. לכן $\mathrm{NP}\subseteq\mathrm P$, וההכלה ההפוכה ידועה.

4. Cook–Levin: מחישוב לנוסחה

SAT ב-NP כי השמה היא תעודה. לקושי, יהי $L\in\mathrm{NP}$ ו-$N$ מכונה המכריעה אותו כך שכל ענף נמשך לכל היותר $T=p(|x|)$ צעדים. הראש מבקר רק ב-$S=O(T)$ תאים. מרפדים ענף מקבל קצר בלולאת קבלה, ומציגים את החישוב כטבלה בגודל $T\times S$: כל שורה היא קונפיגורציה מלאה.

משתני הטבלה

נשתמש באלפבית סופי

כאשר $(q,a)$ מסמן שהראש נמצא בתא, מצב המכונה $q$ והסימן הנקרא $a$. המשתנה

אומר שבתא $i$ בזמן $t$ מופיע $s\in\Gamma'$. למכונה קבועה יש $O(TS)=O(T^2)$ משתנים.

יחידות והתחלה

לכל מיקום דורשים לפחות סימן אחד,

ולכל $s\ne r$ דורשים לכל היותר אחד,

פסוקיות יחידה מקבעות את שורה 0: $q_0$, ביטי $x$, וריקים בשאר התאים. אפשר לדרוש ראש/מצב מסומן יחיד בכל שורה במפורש.

קבלה ומעברים

דורשים הופעת $q_{\mathrm{acc}}$, או דורשים אותו בשורה האחרונה לאחר ריפוד:

צעד TM משנה רק שכונה קבועה סביב הראש. לכן חוקיות בין שתי שורות נקבעת בחלונות קבועי גודל, למשל $2\times3$. לכל תבנית מקומית אסורה $\pi$ מוסיפים פסוקית

יש מספר קבוע של סוגי תבניות לכל $(t,i)$, כי המכונה והאלפבית קבועים. סמני קצה מטפלים בגבולות. הפסוקיות כופות גם העתקת תאים רחוקים וגם מעבר חוקי של הראש והמצב.

נכונות וגודל

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

יש $O(T^2)$ תאי מרחב־זמן ומספר קבוע של פסוקיות לכל תא וחלון. לכן הגודל וזמן הבנייה פולינומיאליים. לאחר מכן ממירים ל-CNF ול-3CNF בעזרת משתני עזר תוך שמירת סיפוקיות וגודל פולינומיאלי.

מה בודק חלון מקומי

נניח שבשורה העליונה מופיעה השכונה

והמעבר $\delta(q,a)$ מרשה ״כתוב $d$, זוז ימינה ועבור למצב $q'$״. השכונה המתאימה בשורה הבאה חייבת להיות

במעבר שמאלה סימון המצב עובר אל הסימן השמאלי. אם הראש אינו בחלון, הסימן האמצעי בשורה התחתונה חייב להיות העתק של הסימן שמעליו. רשימת החלונות החוקיים הסופית כוללת את כל המעברים בטבלת $\delta$ ואת חלונות ההעתקה הרגילים.

כדי לכתוב CNF, מונים כל הצבה אסורה למספר הקבוע של המקומות בחלון. אם ההצבה האסורה הופכת את $L_1,\ldots,L_r$ לאמיתיים, הפסוקית

שוללת בדיוק אותה. $r$ קבוע התלוי במכונה. החפיפה בין חלונות חיונית: הם מסכימים על התאים המשותפים וכך מחברים חוקיות מקומית לשורת יורש גלובלית אחת. בלי חפיפה היה אפשר לצרף קטעים חוקיים בנפרד לשורה שאינה קונפיגורציה עוקבת אפשרית.

חשבון גודל מפורש

נסמן $g=|\Gamma'|$. אילוצי מיקום משתמשים ב-$TS$ פסוקיות ברוחב $g$ עבור ״לפחות אחד״ וב-

פסוקיות בינריות עבור ״לכל היותר אחד״. להתחלה יש $S$ פסוקיות יחידה. דרישת קבלה בשורה האחרונה היא ברוחב לכל היותר $S|\Gamma|$. אם $F$ הוא מספר תבניות החלון האסורות, אילוצי המעבר משתמשים לכל היותר ב-

פסוקיות ברוחב קבוע. $g,F$ תלויים ב-$N$ הקבועה ולא ב-$x$. לכן מספר הפסוקיות ומספר הסמלים הכולל הם $O(TS)=O(T^2)$, פרט לפסוקית קבלה שרוחבה עדיין פולינומיאלי. פיצול פסוקית ברוחב $r$ ל-3CNF מוסיף רק $O(r)$ משתנים ופסוקיות.

5. הוכחה מלאה: 3SAT אל קבוצה בלתי־תלויה

יהי

יוצרים קודקוד לכל הופעת ליטרל. מחברים כל זוג קודקודים מאותה פסוקית, ומחברים בין פסוקיות הופעות משלימות $x,\neg x$. מחזירים $(G_\varphi,k=m)$. יש $3m$ קודקודים ו-$O(m^2)$ צלעות.

כיוון קדימה. מהשמה מספקת בוחרים בכל פסוקית הופעה אמיתית אחת. התקבלו $m$ קודקודים. אין ביניהם צלע פסוקית, כי נבחר אחד מכל פסוקית; ואין צלע סתירה, כי השמה אחת אינה הופכת גם $x$ וגם $\neg x$ לאמיתיים. זו קבוצה בלתי־תלויה.

כיוון אחורה. תהי $S$ קבוצה בלתי־תלויה בגודל $m$. כל גאדג׳ט פסוקית הוא קליקה, ולכן $S$ מכילה לכל היותר קודקוד אחד מכל פסוקית. מכיוון שיש $m$ פסוקיות ו-$m$ בחירות, יש בדיוק אחת מכל פסוקית. אין צלעות סתירה, ולכן הליטרלים הנבחרים עקביים. מציבים אותם כאמיתיים ומשלימים משתנים אחרים שרירותית. בכל פסוקית הליטרל הנבחר אמיתי, ולכן $\varphi$ מספקת.

מכאן

IS ב-NP: מפרטים $k$ קודקודים ובודקים שונות ואי־שכנות. לכן היא NP-שלמה.

דוגמה מלאה בת שלוש פסוקיות

עבור

בונים שלושה משולשים ומציבים $k=3$. מוסיפים קשת סתירה בין $x$ במשולש הראשון ל-$\neg x$ בשני, בין כל הופעה של $y$ לבין $\neg y$ בשלישי, ובין כל זוג משלים אחר. שתי הופעות חיוביות של $z$ אינן סותרות זו את זו.

ההשמה $x=1,y=1,z=1,w=0$ מספקת. אפשר לבחור $x$ מ-$C_1$, את $y$ מ-$C_2$ ואת $z$ מ-$C_3$. הקודקודים במשולשים שונים ואין ביניהם זוג ליטרלים משלימים.

בכיוון ההפוך, כל קבוצה בלתי־תלויה בגודל 3 בוחרת לכל היותר קודקוד אחד מכל משולש. מאחר שיש שלושה משולשים, היא בוחרת בדיוק אחד מכל פסוקית. היא אינה יכולה לבחור, למשל, $y$ מן הראשונה ו-$\neg y$ מן השלישית, כי ביניהם קשת סתירה. שלושת הליטרלים מגדירים השמה חלקית עקבית המספקת את כל שלוש הפסוקיות.

הדוגמה מראה גם מדוע סף 2 אינו מתאים: שני קודקודים יכולים לייצג שתי פסוקיות ולהשאיר את השלישית בלתי־מסופקת. $k=m$ הוא חלק מהאינווריאנט.

6. כיצד כותבים הוכחת רדוקציה

יש לבדוק חמש חובות נפרדות:

1. קלט ופלט: להגדיר את שפות ההכרעה ואת כל הפרמטרים.
2. בנייה: לתאר את $f(x)$ גם לקלט חוקי וגם לקלט פגום.
3. כיוון קדימה: להפוך פתרון מקור לפתרון יעד.
4. כיוון אחורה: לפענח כל פתרון יעד העומד בסף לפתרון מקור.
5. משאבים: לחסום את מספר העצמים, אורכי המספרים וזמן הבנייה באורך הקלט המקודד.

ב-3SAT→IS מתקבלים $3m$ קודקודי הופעות, קשתות פסוקית וסתירה, בחירת הופעה אמיתית מכל פסוקית קדימה, בחירה עקבית מכל פסוקית אחורה, וגודל $O(m^2)$. הפרדת החובות מונעת מציור משכנע של גאדג׳ט להחליף הוכחה.

כיוון החץ דרך פותר היפותטי

דרך בטוחה לבדוק כיוון היא לדמיין קופסה שמכריעה את היעד $B$. אם ברצוננו לפתור מקור $A$, עלינו לחשב $f(x)$, להזין אותו לקופסת $B$ ולהחזיר את תשובתה. לכן נדרש $A\le_m^pB$. אם התהליך שכתבנו מתחיל במופע של $B$ ומשתמש בפותר של $A$, הוכחנו את החץ ההפוך.

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

רשת רדוקציות במקום הוכחה מחדש

לאחר שהוכחנו

טרנזיטיביות נותנת $\mathrm{SAT}\le_m^p\mathrm{IS}$. אין צורך להטמיע מחדש את טבלת Cook–Levin בתוך גאדג׳ט הגרף. זו התועלת המעשית בשלמות: אחרי בעיית המקור האוניברסלית, אפשר להתחיל כל הוכחה מבעיה שלמה שמבנה הפתרון שלה דומה ליעד.

רדוקציה גם אינה מוכיחה שהיעד קשה ממש מן המקור במובן של חסם זמן חד. היא אומרת שאלגוריתם מהיר ליעד היה נותן אלגוריתם מהיר למקור בתוספת תקורה פולינומיאלית. אלגוריתם מהיר למקור אינו אומר דבר בכיוון ההפוך, ואין מכאן לבדה הפרדה בין סיבוכויות.

טעויות נפוצות

1. להפוך את חץ הקושי.
2. להוכיח רק כיוון אחד.
3. להתעלם מקלט פגום או מגודל פלט.
4. להכריז שלמות בלי שייכות ל-NP.
5. לתאר את Cook–Levin כ״טבלה״ בלי אילוצים וניתוח גודל.
6. לשכוח קשתות פסוקית או קשתות סתירה.
7. לא להסביר מדוע גודל $m$ כופה בחירה מכל פסוקית.

תרגילים

תרגיל 1 — כיוון הקושי

תהי $A\le_p B$. הוכיחו: אם $B\in\mathrm P$ אז $A\in\mathrm P$. הסבירו מה ״עובר אחורה״ ומה ״הולך קדימה״ בחץ הרדוקציה.

תרגיל 2 — שתי חובות לשלמות

הגדירו NP-שלמות. הוכיחו מדוע שייכות ל-$\mathrm{NP}$ לבדה או קושי לבדו אינם מספיקים.

תרגיל 3 — חלונות מקומיים ב-Cook–Levin

הסבירו מדוע די באילוצים על חלונות מקומיים בטבלת החישוב כדי לאכוף חישוב חוקי של TM.

תרגיל 4 — $k=m$ ברדוקציית 3SAT→IS

ברדוקציה הסטנדרטית מ-3SAT לקבוצה בלתי־תלויה עם פרמטר $k=m$ (מספר פסוקיות), הוכיחו מדוע בחירת $k<m$ שוברת את השקילות.

תרגיל 5 — טרנזיטיביות וגודל פלט

הוכיחו ש-$\le_p$ טרנזיטיבית, והדגישו מדוע נדרש ש-$|f(x)|$ יהיה פולינומיאלי.

סיכום

רדוקציה היא מהדר מופעים עם כיוון. שלמות דורשת שייכות וקושי; טעויות כיוון וגודל הן מלכודות בחינה.

תרגול מודרך

משימה 1 — הפרכת כיוון שגוי

סטודנט ״מוכיח״ $B$ קשה על ידי רדוקציה $B\le_p A$ כאשר $A$ קלה. מה שגוי?

משימה 2 — רדוקציה חלקית

ברדוקציה לגרף: הוכח רק ״אם נוסחה סבירה אז יש קבוצה בלתי־תלויה״. אילו סעיפים חסרים?

משימה 3 — מ-Cook–Levin לשלמות 3SAT

סכמו כיצד עוברים מ-SAT ל-3SAT תוך שמירת NP-שלמות (רעיון הגאדג׳ט, לא הוכחה מלאה).

מקורות

עדויות הקורס

• תמליל 9 של סמסטר א׳ הנוכחי: רדוקציות many-one פולינומיאליות, כיוון, טרנזיטיביות וסגירות.
• תמליל 10: NP-קושי, NP-שלמות ותוצאותיו של אלגוריתם פולינומיאלי לבעיה שלמה.
• תמלילים 12–13: טבלת החישוב של Cook–Levin, עקביות מקומית, קבלה וחשבון גודל פולינומיאלי.
• תמליל 14: גאדג׳טי גרפים מ-SAT/3SAT, ובכללם הבנייה לקבוצה בלתי־תלויה.
• הסיכום הממוזג, עמ׳ 43–49: רדוקציות פולינומיאליות ושלמות; עמ׳ 50–54: Cook–Levin בלבד; עמ׳ 55–57, 64–66 ו-72–75: משפחת בעיות הגרף והרדוקציות ביניהן. אין לייחס לטווחים אלה כיסוי רחב יותר.

אימות מספרי לימוד

• Sipser, מהדורה שלישית, §§7.4–7.5, עמ׳ 300–325.
• Arora–Barak (טיוטה), §2.3, עמ׳ 45–58.
• Papadimitriou, פרקים 8–9. המשפטים אומתו בספרים; הסימון וסדר ההצגה תואמים לקורס.