משפט לדנר, או - מפרקים לגורמים את NP

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

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

אנחנו מכירים בעיות רבות ששייכות ל-P, כלומר בעיות ששיכות ל-NP והן “הכי קלות” שם. על קצה המזלג: חישוב אריתמטי, חיפוש ברשימה, מיון, חיפוש בגרף, מציאת עץ פורש של גרף, התמרת פורייה בדידה, מציאת קמור של קבוצת נקודות, פתרון בעיית תכנון לינארי, ועוד ועוד ועוד ועוד - וגולת הכותרת של תחילת העשור: בדיקת ראשוניות. לא כל אלו הן בעיות כן/לא אבל העיקרון ברור). בדומה, אנחנו מכירים בעיות רבות שהן NP-שלמות - כלומר, בעיות ב-NP שהן “הכי קשות”. ושוב, רשימת המכולת כוללת את SAT, את 3-צביעה של גרפים, מציאת מעגל המילטוני, פתרון בעיית תכנון לינארי בשלמים, ועוד ועוד ועוד. אבל מה אנחנו לא מכירים כרגע בכלל? בעיות ב-NP שהן לא ב-P וגם אינן NP-שלמות.

צריך להבהיר כאן משהו: אין לנו כרגע מושג האם P שונה מ-NP. אם שתי המחלקות הללו שוות, אז כל בעיה ב-NP היא גם NP-שלמה, וגם ב-P (למעשה, שתי השפות ה”טריוויאליות” - שפת כל המילים והשפה הריקה - אינן NP-שלמות בגלל בעיה טכנית לא חשובה, אבל נעזוב את זה). אם כן, לשאלה האם יש שפה שאינה ב-P וגם אינה NP-שלמה. כלומר, האם העולם שלנו כולל רק בעיות “הכי קלות” ובעיות “הכי קשות”, או שיש גם בעיות “הכי בינוניות”?

יש לנו כרגע מועמדת טבעית לתפקיד בעיה שכזו - בעיית הפירוק לגורמים. לא ידוע אלגוריתם פולינומי לבעיה זו, ובניגוד לבדיקת ראשוניות - גם לא ממש מצפים שאלגוריתם כזה יימצא. עם זאת, ולמרות שזו תהיה סנסציה של ממש, אני לא חושב שהאפשרות לכך שזה יקרה נפסלת על הסף (למעשה, קיים אלגוריתם פולינומי לפירוק לגורמים, אבל למחשבים קוונטיים). מפתיע עוד יותר יהיה לגלות שפירוק לגורמים היא בעיה NP-שלמה. אבל כאמור, להוכיח שפירוק לגורמים זו בעיית ביניים שכזו בפרט יפתור לנו אחת ולתמיד את סוגיית \( \mbox{P=NP} \), ולא ממש סביר שכך זה יקרה…

אז מה כן אפשר לעשות? הוכחה שמתבססת על ההנחה ש-\( \mbox{P}\ne\mbox{NP} \), כמובן, וזה מה שאציג כעת. לרוע המזל, ההוכחה אינה פשוטה; למרבה המזל, היא גם לא כל כך קשה כמו הוכחה אחרת שקראתי בשעתו. ההוכחה הזו קלה מספיק כדי שאציג אותה בבלוג, ולו כדי לנקום במי שרוצים דברים קשים יותר.

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

שפת הביניים שנבנה תתבסס על \( \mbox{SAT} \); כזכור (מי שלא זוכר, אולי עדיף שלא ימשיך…), SAT היא פשוט אוסף של פסוקי \( \mbox{CNF} \) ספיקים, והיא האמא של השפות ה-NP-שלמות, ולכן בוחרים אותה, אבל אפשר היה לקחת כל שפה NP-שלמה אחרת במקומה. הרעיון הוא לקחת מילים ב-SAT ו”לנפח” את האורך שלהן על ידי הוספת ג’יבריש לא מזיק - נניח, תווי \( x \), שמן הסתם לא מהווים חלק מקידוד של פסוק חוקי. בשביל מה זה טוב? כי אם נוסיף המון תווי \( x \) לפסוק, זה “ישפר”את זמן הריצה של אלגוריתמים עליו; זמן הריצה נמדד ביחס לאורך המילה כולה, כולל הדולרים, אבל זמן הריצה של האלגוריתם ינבע רק מאורך הפסוק עצמו, כי מהדולרים הוא מתעלם… זה נראה כמו רמאות מוחלטת וכמו משהו מטופש מאין כמותו, אני יודע; זו אחת הסיבות שבגללן ההוכחה הזו כה מגניבה.

פורמלית, נניח ש-\( H\left(n\right) \) היא פונקציה מהטבעיים לטבעיים, אז נסמן \( \mbox{SAT}_{H}\triangleq\left\{ \varphi \$^{n^{H\left(n\right)}}|\varphi\in\mbox{SAT},\left|\varphi\right|=n\right\} \). כלומר, אנחנו “מרפדים” כל \( \varphi\in\mbox{SAT} \) על ידי הוספת \( n^{H\left(n\right)} \) תווי זבל, כאשר \( n \) הוא האורך של \( \varphi \). ה-\( H\left(n\right) \) שבה נשתמש, שאגדיר אותה בהמשך, תקיים את התכונות הבאות: ראשית, אפשר יהיה לחשב אותה בזמן “סביר”. שנית, היא תהיה מונוטונית עולה; ושלישית, והכי חשוב, היא תהיה חסומה אם ורק אם \( \mbox{SAT}_{H}\in\mbox{P} \).

כאן נמצא לב ההוכחה. אם \( H \) הייתה גדלה מהר, אז היא הייתה גורמת לניפוח אדיר של מילים מ-\( \mbox{SAT} \) ואז לא היה שום דבר מפתיע בכך ש-\( \mbox{SAT}_{H}\in\mbox{P} \). כי, למשל, אם אני מקבל קלט \( \varphi \$^{2^{n}} \), אז גם אם אבדוק את כל ההשמות האפשריות ל-\( \varphi \) זה ייקח לי זמן של \( O\left(2^{n}\right) \) בלבד, וזהו האורך של המילה \( \varphi \$^{2^{n}} \) - כלומר, יש לי אלגוריתם “לינארי” שפותר את \( \mbox{SAT}_{H} \), אבל כמובן שלא עשיתי פה שום דבר חכם. אם כן, העובדה שדווקא כאשר \( H \) חסומה, ולכן הניפוח שלנו את \( \mbox{SAT} \) הוא לא יותר מפולינומי בגודלו, דווקא אז \( \mbox{SAT}_{H}\in\mbox{P} \) - זו עובדה משונה מאוד שלא כל כך מפתיע שגוררת את התוצאה שאנו מחפשים.

בואו נראה למה.

ראשית, אם \( \mbox{SAT}_{H}\in\mbox{P} \) אז כאמור \( H \) חסומה, כלומר \( H\left(n\right)<c \) עבור קבוע \( c \) כלשהו ולכן \( \mbox{SAT}_{H} \) כוללת פסוקים שהניפוח שלהם הוא בסך הכל פולינומי. זה מאפשר לנו לבצע רדוקציה פשוטה של \( \mbox{SAT} \) אל \( \mbox{SAT}_{H} \): בהינתן \( \varphi \), צריך לייצר ממנו את \( \varphi\$^{n^{H\left(n\right)}} \) אבל את זה קל לעשות - אמרתי שקל לחשב את \( H\left(n\right) \), ומכיוון שצריך לכתוב רק מספר פולינומי של תווים אחרי \( \varphi \), הרדוקציה תהיה פולינומית (אם למשל היה צריך לכתוב \( 2^{n} \) תווים, הרדוקציה לא הייתה פולינומית והכל היה קורס). אם כן, מאחר והנחנו ש-\( \mbox{SAT}_{H}\in\mbox{P} \) והראינו רדוקציה פולינומית של \( \mbox{SAT} \) אל \( \mbox{SAT}_{H} \), אז גם \( \mbox{SAT}\in\mbox{P} \) מה שגורר \( \mbox{P=NP} \), בסתירה להנחה שלנו ש-\( \mbox{P}\ne\mbox{NP} \).

מצד שני, אם \( \mbox{SAT}_{H} \) היא \( \mbox{NP} \)-שלמה, זה אומר (מהגדרת המושג של \( \mbox{NP} \)-שלמות) שיש רדוקציה פולינומית מ-\( \mbox{SAT} \) אליה. טוב, הפעם זה לא מוביל מייד לסתירה כי הרי לא ניתן להסיק מכך ש-\( \mbox{SAT}\in\mbox{P} \), אז מה כן? ובכן, הרדוקציה היא פולינומית? נניח שיש לה חסם זמן ריצה של \( c\cdot n^{d} \).

עכשיו נעשה תעלול חביב ביותר - רדוקציה עצמית של \( \mbox{SAT} \). נראה אלגוריתם שבהינתן פסוק \( \varphi \) שאנו רוצים לבדוק את שייכותו ל-\( \mbox{SAT} \), מצליח לחלץ ממנו פסוק \( \psi \) ששייך ל-\( \mbox{SAT} \) אם ורק אם \( \varphi \) שייך ל-\( \mbox{SAT} \), וכמו כן \( \left|\psi\right|<\left|\varphi\right| \). ההקטנה הזו היא קריטית - זה אומר שנוכל לחזור על התהליך שוב ושוב ובכל סיבוב להקטין בביט אחד את מה שיש לבדוק, ועל כן תוך מספר לינארי של סיבובים הפסוק שאנו בודקים יהיה קטן מספיק כדי שניתן יהיה לבדוק אותו באופן ישיר בלי לחשוש מהשלכות קטסטרופליות על זמן הריצה. הרעיון של רדוקציות עצמיות מקצרות אורך שכאלו הוא רעיון יפה וחשוב בפני עצמו ואני שמח שהוא צץ כך באמצע ההוכחה הזו.

טוב, אז איפה היינו? אה, כן, \( \mbox{SAT}_{H}\notin\mbox{P} \) (כי היא \( \mbox{NP} \)-שלמה והנחנו ש-\( \mbox{P}\ne\mbox{NP} \)). ולכן מהתכונה החשובה של \( H\left(n\right) \) שדיברתי עליה עולה ש-\( H\left(n\right) \) לא חסומה. מכיוון שהיא גם מונוטונית עולה, נקבל שקיים \( n_{0} \) כך שלכל \( n>n_{0} \) מתקיים \( n^{H\left(n\right)}>c\cdot n^{2d} \). במילים אחרות - הניפוח הוא יחסית גדול.

אלא מה? הרדוקציה של \( \mbox{SAT} \) ל-\( \mbox{SAT}_{H} \) לוקחת פסוק \( \varphi \) כך ש-\( \left|\varphi\right|=n>n_{0} \) ומייצרת אחד משני דברים: או משהו שנראה כמו \( \psi \$^{\left|\psi\right|^{H\left(\left|\psi\right|\right)}} \), כאשר \( \psi \) הוא פסוק חוקי (כי כך נראית מילה ב-\( \mbox{SAT}_{H} \)), או משהו שבכלל לא מהצורה הזו (אין בו את הכמות הנכונה של דולרים, או שהוא בכלל נראה שונה לגמרי). במקרה שהמשהו לא מהצורה הנכונה, ברור לנו שהוא לא שייך ל-\( \mbox{SAT}_{H} \) ולכן \( \varphi \) לא שייך ל-\( \mbox{SAT} \) וסיימנו. אז נניח מעתה ואילך שהרדוקציה תמיד מייצרת משהו מהצורה הנכונה. השאלה שלנו היא - כמה גדול \( \psi \) יכול להיות? התשובה היא שלא ממש גדול, בגלל שלא היה לרדוקציה הרבה זמן כדי לכתוב את \( \psi\$^{\left|\psi\right|^{H\left(\left|\psi\right|\right)}} \), והיו לה המון דולרים לכתוב…

פורמלית, בואו נסמן \( \left|\psi\right|=k \). הרדוקציה פעלה על \( \varphi \) בזמן \( c\cdot n^{d} \) לכל היותר, ולכן זה המספר המקסימלי של תווים שהיא יכלה לכתוב - כלומר, \( \left|\psi \$^{k^{H\left(k\right)}}\right|\le c\cdot n^{d} \). מצד שני, \( \left|\psi \$^{k^{H\left(k\right)}}\right|=k+k^{H\left(k\right)}>c\cdot k^{2d} \). כלומר, קיבלנו \( c\cdot k^{2d}<c\cdot n^{d} \). מכאן חיש קל עולה ש-\( k=\sqrt{n} \). כלומר, קיצרנו מאוד את \( \varphi \), ולכן ניתן להשתמש בתעלול הרדוקציה העצמית.

הפסקה. מישהו עדיין עוקב? כי עכשיו הגענו לחלק המסובך בהוכחה - הבניה של \( H \). למי שבאמת שרד עד לכאן - קחו נשימה עמוקה. ועכשיו בואו ונתחיל.

ראשית, נמספר את כל מכונות הטיורינג: \( M_{k} \) תהיה המכונה ה-\( k \)-ית בסדר הלקסיקוגרפי על כל קידודי המכונות. כעת נגדיר את \( H\left(n\right)=k \) להיות ה-\( k \) הקטן ביותר שמקיים \( k<\log\log n \) וגם ש-\( M_{k} \) מכריעה את \( \mbox{SAT}_{H} \) עבור \( x \)-ים המקיימים \( \left|x\right|\le\log n \), בזמן ריצה \( k\left|x\right|^{k} \) לכל היותר. אם אין מכונה כזו, אז \( k=\log\log n \).

ההגדרה נראית מעגלית, אך מכיוון שכדי להגדיר את \( H\left(n\right) \) עלינו להכיר רק ערכים של \( H \) הקטנים או שווים ל-\( \log n \) אין כאן מעגליות (זוהי הגדרה רקורסיבית, לא מעגלית).

אם אתם תוהים כרגע מה לעזאזל - כן, גם אני הרגשתי ככה בהתחלה. אבל ההגדרה לא באמת כזו נוראית, וכל הלוגים המפחידים קיימים שם מסיבה טובה - אנחנו רוצים שאפשר יהיה לחשב את \( H\left(n\right) \) ביעילות. החישוב הזה הוא עניין ישיר למדי - פשוט עוברים בהרצה מבוקרת על כל המכונות \( M_{1},\dots,M_{\log\log n} \) ולכל מכונה, מריצים אותה על כל הקלטים \( x \) המקיימים \( \left|x\right|\le\log n \). בנוסף צריך לבדוק באופן ישיר האם \( x\in\mbox{SAT}_{h} \) - זאת עושים באמצעות פתרון בכוח גס של \( \mbox{SAT} \) וחישוב רקורסיבי של \( H\left(n\right) \) לגדלים קטנים יותר. זו פשוט הפעלת כוח גס באופן הברוטלי ביותר האפשרי, וזה יוצא יעיל בזכות הלוגים.

עכשיו, אם \( H \) אינה מונוטונית עולה אז יש \( n \) כך ש-\( H\left(n\right)=k \) אבל \( H\left(n+1\right)<k \). מכאן בפרט ש-\( H\left(n+1\right)\ne\log\log\left(n+1\right) \) (כי \( k\le\log\log n \)), כלומר \( H\left(n+1\right) \) הוא מספרה של מכונה שעונה “כמו שצריך” על כל הקלטים עד גודל \( \log\left(n+1\right) \). אבל מכונה כזו עונה נכון על כל הקלטים עד גודל \( \log n \) ולכן \( H\left(n\right) \) היה צריך להיות קטן או שווה למספרה הסידורי - סתירה.

הראנו כי \( H\left(n\right) \) ניתנת לחישוב יעיל ושהיא מונוטונית עולה. נותר להבין מדוע \( H\left(n\right) \) אכן מקיימת את תכונת החסימות. ראשית נניח כי \( \mbox{SAT}_{H}\in\mbox{P} \) ונוכיח כי \( H \) חסומה. אם \( \mbox{SAT}_{H}\in\mbox{P} \) אז יש אינסוף מכונות פולינומיות המכריעות את \( \mbox{SAT}_{H} \) בזמן \( cn^{c} \) עבור \( c>0 \) קבוע גדול דיו; תהא \( M_{k} \) מכונה שכזו כך ש-\( k>c \). אז בפרט \( M_{k} \) מכריעה את \( \mbox{SAT}_{H} \) עבור קלטים המקיימים \( \left|x\right|\le\log n \) בזמן ריצה \( k\left|x\right|^{k} \) לכל \( n \); מכאן ש-\( H\left(n\right)\le k \) לכל \( n \) שעבורו \( k\le\log\log n \), כלומר לכל \( n>2^{2^{k}} \), כלומר \( H \) חסומה.

בכיוון השני, אם \( H \) חסומה נוכיח ש-\( \mbox{SAT}_{H}\in\mbox{P} \) באופן הבא: מכיוון ש-\( H\left(n\right) \) חסומה, מעקרון שובך היונים יש ערך \( k \) שאותו היא מקבלת אינסוף פעמים, והדבר גורר ש-\( M_{k} \) מכריעה את \( \mbox{SAT}_{H} \) בזמן \( k\cdot n^{k} \). כדי לראות זאת, נניח שעל קלט \( x \) כלשהו, \( M_{k} \) לא עוצרת עם התשובה הנכונה בזמן \( k\cdot\left|x\right|^{k} \), אז על פי הגדרת \( H \) בהכרח \( H\left(n\right)\ne k \) לכל \( n>2^{\left|x\right|} \) - סתירה.

זו סוף ההוכחה.

בקריאה מחודשת, ההוכחה הזו היא למעשה פשוטה למדי. אין בה יותר מדי פרטים, ההגדרה היא יחסית ישירה, ואין צורך בטיעונים מחוכמים כל כך בשביל להתקדם. הוכחות כאלו הן נפוצות למדי בתורת הסיבוכיות, ואחרי שמתרגלים אליהן, הן באמת לא נוראיות כל כך. כך זה באופן כללי במתמטיקה - הוכחות שלצופה מבחוץ נראות מזוויעות לחלוטין, נראות פשוטות למדי למישהו “מבפנים”. עבורי, ככותב בלוג מתמטי, הוכחות כאלו מהוות בעיה מהותית. מצד אחד לטעמי הן יפהפיות וקלות להבנה ומן הראוי שאציג אותן לכל דורש; מצד שני, ברור לי לחלוטין שרובם המוחץ של הקוראים לא ישרדו יותר מכמה שורות של ההוכחה - ולמה שישרדו? הרי הם לא קוראים ספר לימוד בסיבוכיות וקשה להם להתעמק בפרטים, שאותם אני כנראה לא מציג באופן טוב כפי שספר לימוד מסוגל. אני לא מסוגל לפשט מהותית את ההוכחה או לתת הרבה הסברים אינטואיטיביים לה - כאן ההבנה מגיעה משליטה בטכניקה עצמה.

אז טוב שלפעמים מפצירים בי לכתוב משהו מתקדם ונותנים לי תירוץ לכתוב פוסט כזה כעונש. כמובן, אנסה גם לכתוב פוסטים יותר “סקירתיים”ופחות טכניים על נושאים מתקדמים, אבל יותר קל להבטיח מלקיים; בפרט, בהתחשב בכך שהידע המתמטי שלי הוא לא רחב עד כדי כך (גם אם הבלוג אולי נותן אשלייה שגויה שאין זה כך).