על P=NP מעל חבורות אבליות - מבוא שלם

בואו נוכיח ש-\( \mbox{P}\ne\mbox{NP} \).

אה… מה?

תיארתי בעבר בבלוג את בעיית \( \mbox{P=NP} \) בתור הבעיה הפתוחה המרכזית במדעי המחשב ולא הרבה השתנה מאז - עדיין אין לנו הוכחה ש-\( \mbox{P}\ne\mbox{NP} \) למרות שרוב מדעני המחשב חושבים שזה המצב. אז מן הסתם לא על הבעיה הזו אני רוצה לדבר. אני רוצה לדבר על \( \mbox{P}\ne\mbox{NP} \) מעל מודל חישוב אחר, אבל כזה שלדעתי לא שונה יותר מדי באופיו ממודל החישוב הרגיל (אם כי אחרים - למשל, אני - עשויים לחלוק עלי ולטעון שיש הבדלים מהותיים ביותר ושנראה אותם עוד בפוסט הזה). פורמלית מה שארצה להראות הוא שלכל חבורה אבלית אינסופית \( G \) מתקיים \( \mbox{P}_{G}\ne\mbox{NP}_{G} \) כאשר \( \mbox{P}_{G},\mbox{NP}_{G} \) הן מחלקות הסיבוכיות הרלוונטיות מעל החבורה \( G \). כמובן שתכף אגדיר את הכל במפורש, אבל רק כדי שנהיה סגורים על האופן שבו התוצאה הזו מתקשרת לתורת הסיבוכיות הרגילה: במקרה שבו \( G=\mathbb{Z}_{2} \) אנו מקבלים את המחלקות \( \mbox{P},\mbox{NP} \) ה”רגילות”.

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

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

הרעיון הוא זה: קחו את שפת התכנות החביבה עליכם. אפשר להשתמש בה כמות שהיא - יש לנו משתנים שהם מספרים, מחרוזות, ערכים בוליאניים… הכל כרגיל. יש לכם גם את כל פונקציות הספריה שאתם מכירים ואוהבים והכל טוב ויפה. אלא שבנוסף לכך יש מחלקה בשם \( G \) שאין לכם גישה להגדרות הפנימיות שלה. כל מה שיש לכם הוא קבוע \( e\in G \), ולמשתנים ששייכים למחלקה \( G \) יש שלוש מתודות - האחת, \( = \), מקבלת משתנה נוסף השייך למחלקה \( G \) ומחזירה \( \mbox{True} \) אם הם שווים ואחרת \( \mbox{False} \); השניה, \( + \), מקבלת משתנה נוסף השייך למחלקה \( G \) ומחזירה את החיבור של שתיהן, על פי כלל החיבור בחבורה \( G \), ומובטח לנו ש-\( a+e=e+a=a \) לכל \( a\in G \), והשלישית, \( - \), מקבלת משתנה אחד \( a \) השייך למחלקה \( G \) ומחזירה משתנה אחר \( -a \), כך שמובטח שמתקיים \( a+\left(-a\right)=e \). אין לכם יכולת לחבר איברים של \( G \) עם משתנים מסוג אחר (למשל, עם מספרים שלמים) או להשוות אותם למספרים מסוג שונה; אברי \( G \) הם סוג של “קופסה שחורה”.

כל בעיה חישובית מהסוג שעליו נרצה לדבר כאן תהיה מהסוג הבא: אנחנו מקבלים כקלט מערך של משתנים מתוך \( G \), שאורכו ידוע רק בזמן ריצה (כלומר, אנחנו צריכים להתמודד עם מערך מאורך כלשהו) וצריכים להחזיר כפלט \( \mbox{True} \) או \( \mbox{False} \), בהתאם לתכונה שהמערך הזה מקיים או לא מקיים. בואו נציג מייד דוגמה לבעיה כזו כדי שיהיה ברור - זו תהיה הבעיה המרכזית שנעסוק בה בפוסט. במאמר קוראים לה Nullsack (וריאציה על Knapsack, למי שמכיר).

\( \Sigma_{G}=\left\{ \left(x_{1},\dots,x_{n}\right)\in G^{n}\ |\ n\in\mathbb{N}\wedge\exists J\ne\emptyset:\sum_{i\in J}x_{i}=e\right\} \)

מילולית, ב-\( \Sigma_{G} \) כלולים כל הוקטורים מאורך \( n \) טבעי כלשהו (כלומר, יכולים להיות שם וקטורים מאורך 1, מאורך 10, מאורך \( 10^{100} \) וכן הלאה) שאפשר לסכום חלק מהאיברים בהם ולקבל את \( e \). במקרה שבו \( G=\mathbb{Z} \), זו השאלה הבאה: נותנים לכם אוסף של מספרים שלמים (לא קבוצה במובן המתמטי, כי אותו מספר יכול להופיע כמה פעמים) - האם אפשר לבחור מתוכו תת-אוסף של מספרים שהסכום שלהם הוא 0?

הבעיה הזו היא בעיה מוכרת מאוד בתורת הסיבוכיות: היא נקראת Subset-Sum והיא דוגמה פשוטה ושימושית לבעייה חישובית שהיא NP-שלמה. אלא שיש הבדל קריטי שחייבים לתת עליו את הדעת מייד: במודל הרגיל של תורת הסיבוכיות (מכונת טיורינג “רגילה”), הקלט ל-Subset-Sum נתון בתור סדרה של ביטים שמקודדת את וקטור המספרים, וזמן הריצה של האלגוריתם נמדד ביחס לאורך סדרת הביטים הזו. לעומת זאת, במודל החדש שהצגתי, זמן החישוב נמדד תמיד ביחס למספר \( n \) ותו לא, והקלט נתון לנו בתור “קופסה שחורה”. ההבדל הזה הוא קריטי. אנסה לתת דוגמה: נניח שהחבורה שלנו \( G \) היא אכן \( \mathbb{Z} \). אז אם האיבר \( a\in G \) היה מיוצג בתור סדרת ביטים, היינו יכולים לחלק אותו ב-2 בקלות, על ידי הסרת הביט הימני ביותר ממנו. במודל החדש אין לי מושג איך אפשר לחלק את המספר ב-2. ונניח (רק לצורך ההמחשה) שאיכשהו יש לי משתנה מהמחלקה \( G \) שידוע לי שמכיל את הערך \( 1 \), ויש לי משתנה אחר \( a \) שידוע לי שהוא חזקה כלשהי של \( 2 \) ואני רוצה “לגלות” מה הערך המספרי שלו. אז אפשר לחבר את 1 ל-1 ולקבל 2, ואת 2 ל-2 ולקבל 4, ואת 4 ל-4 ולקבל 8 וכך הלאה לקבל חזקות של \( 2 \) ובכל פעם להשוות ל-\( a \). מספר הפעולות שיידרש לנו לעשות את זה הוא מאותו סדר גודל של מספר הביטים שנדרשים כדי לייצג את \( a \), דהיינו זה זמן ריצה לינארי בגודל הייצוג של \( a \), כלומר במודל הקלאסי, אבל זה זמן ריצה לא חסום במספר הקלטים שלנו, כלומר במודל ה”חדש”. בכל מקרה, אני מקווה שכבר קיבלתם את התחושה שחישובים במודל החדש הם יותר קשים מאשר במודל הרגיל, בגלל שהקלט פחות נגיש לנו.

למי שעדיין לא הבין את ההבדלה הזו, לא נורא - בהמשך נראה בדיוק איך היא רלוונטית לנו.

עכשיו אפשר להגדיר את \( \mbox{P}_{G} \): אלו כל בעיות ההכרעה שניתן לפתור במודל החישובי מעל \( G \) בזמן שהוא פולינומי באורך הקלט (כלומר, באורך של וקטור הקלטים שהתקבל). אבל עדיין צריך להגדיר את \( \mbox{NP}_{G} \). וכאן יש לנו דילמה כלשהי. בואו ניזכר שניה בהגדרה של \( \mbox{NP} \) הרגילה: אנחנו אומרים ש-\( L\in\mbox{NP} \) אם קיים אלגוריתם פולינומי \( M \) שמקבל שני סוגי קלטים: הקלט ה”רגיל”, שמסומן ב-\( x \), וקלט שהוא “עד”, או “הוכחה” לשייכות של \( x \) ל-\( M \), שמסומן \( y \). הפולינומיות של \( M \) היא ביחס לגודל הייצוג של \( x \), וגם \( x \) וגם \( y \) הם סדרות של ביטים (מכאן יוצא שאפשר להניח שהגודל של \( y \) יהיה גם הוא פולינומי בגודל הייצוג של \( x \) כי אחרת \( M \) ממילא לא הייתה מצליחה לקרוא את הכל ולעמוד במגבלות הזמן שלה). אנו דורשים שאם \( x\in L \) אז יהיה \( y \) כלשהו כך ש-\( M\left(x,y\right)=\mbox{True} \), אבל שאם \( x\notin L \) אז לכל \( y \) שהוא, \( M\left(x,y\right)=\mbox{False} \). למשל, ב-Subset-Sum ה-\( x \) הוא וקטור של מספרים שלמים, ואילו \( y \) הוא קבוצת האינדקסים \( J \) שיש לסכום, במקרה שבו אכן קיימת קבוצה כזו.

הדילמה שעומדת בפנינו היא זו: בהינתן \( x \) שהוא וקטור של אברי \( G \), מה יהיה \( y \)? הוא יכול להיות וקטור של אברי \( G \) בעצמו, והוא גם יכול להיות סתם וקטור של ביטים. די בבירור המקרה הראשון חזק יותר מהשני (כי וקטור ביטים ודאי שאפשר “לקודד” בעזרת וקטור של אברי \( G \): 0 יהיה \( e \) ו-1 יהיה כל איבר שאינו \( e \)) ולא ברור אוטומטית מה ההגדרה ה”נכונה”. מכיוון שהתוצאה שאנחנו רוצים להראות היא ש-\( \mbox{P}_{G}\ne\mbox{NP}_{G} \), כלומר ש-\( \mbox{NP}_{G} \) היא מחלקה גדולה יותר, הרי שאם נראה את זה עבור ההגדרה של “עד” שמקודד על ידי ביטים, בוודאי שהתוצאה תנבע גם עבור “עד” שמקודד על ידי אברי \( G \). לכן נשתמש בהגדרה-מבוססת-הביטים בפוסטים על הנושא.

שימו לב שבבירור Subset-Sum שייך ל-\( \mbox{NP}_{G} \): בהינתן וקטור \( x=\left(x_{1},\dots,x_{n}\right) \), ה-\( y \) שלנו יהיה סדרה של \( n \) ביטים \( \left(b_{1},\dots,b_{n}\right) \) כך ש-\( \sum b_{i}x_{i}=e \). את החישוב קל מאוד לבצע, כמובן. לכן כל מה שנשאר לעשות הוא להשתכנע ש-Subset-Sum אינה שייכת ל-\( \mbox{P}_{G} \), כלומר שאף אלגוריתם לא יוכל לפתור את הבעיה בזמן פולינומי. וכאן מן הסתם יהיה עיקר הסיבוך - איך אפשר לטעון טענה כל כך כללית, על כל אלגוריתם, מחוכם ומסובך ככל שיהיה?

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

נראה איך אפשר לעשות דבר כזה במקרה הפרטי שבו \( G=\mathbb{Z} \). אחר כך נראה איך עושים את זה עבור עוד מחלקה מעניינת של חבורות, ואז ננטוש את הסיבוכיות ונעבור לדבר על תורת המודלים ונשתמש בתעלול מתוכה כדי להראות שההוכחות שלנו יעבדו עבור כל חבורה. אבל לעת עתה, בואו נתמקד במקרה של \( G=\mathbb{Z} \). מה קורה כאן?

ובכן, האלגוריתם מקבל קלטים, \( \left(x_{1},\dots,x_{n}\right) \). הוא יכול לבצע עליהם פעולות חיבור וחיסור ולקבל איברים חדשים שהם צירופים לינאריים של \( \left(x_{1},\dots x_{n}\right) \) עם מקדמים מתוך \( \mathbb{Z} \). כלומר, איבר כללי ב-\( G \) שהמשתמש יכול לבנות הוא מהצורה \( \sum_{i=1}^{n}a_{i}x_{i} \) כך ש-\( a_{i}\in\mathbb{Z} \) (האלגוריתם גם יכול לחבר או לחסר את \( e \) לכל זה, אבל זה לא ישפיע על ערך הסכום ולכן לא צריך להתייחס לזה).

חישובים זה טוב ויפה, אבל מה שמשפיע על ריצת האלגוריתם בסופו של דבר הם ערכים בוליאנים - זה מה שמשפיע על התפצלויות בתוכנית ועל לולאות. הדרך היחידה להפיק ערכים בוליאנים מתוך איברי \( G \) היא באמצעות פונקציית ה-\( = \). על שני איברים כלליים, החישוב יבדוק אם \( \sum_{i=1}^{n}a_{i}x_{i}=\sum_{i=1}^{n}b_{i}x_{i} \), כאשר \( a_{i},b_{i}\in\mathbb{Z} \). אפשר לפשט את זה - הבדיקה הזו שקולה לבדיקה האם \( \sum_{i=1}^{n}\left(a_{i}-b_{i}\right)x_{i}=0 \), או בסימון אחר - האם \( \sum_{i=1}^{n}c_{i}x_{i}=0 \) כאשר \( c_{i}\in\mathbb{Z} \). בסימון עוד יותר קומפקטי: האם \( c\cdot x=0 \), כאשר \( c \) ו-\( x \) שניהם וקטורים והמכפלה היא מכפלה סקלרית “רגילה”.

בואו ניקח עכשיו אלגוריתם פולינומי קונקרטי ונחסל אותו. נשחק איתו את המשחק הבא: נתחיל להריץ אותו וניתן לו לעשות איזה חישובים שבא לו, אבל בכל פעם שהוא בודק שוויון בין שני איברים של \( G \) נענה לו “לא”, אלא אם זה שוויון טריוויאלי לחלוטין - כזה שבו במשוואה \( \sum_{i=1}^{n}c_{i}x_{i}=0 \) המתאימה כל ה-\( c_{i} \)-ים הם 0 (למשל, אם הוא שואל האם \( x_{1}=x_{1} \)). האלגוריתם ירוץ ירוץ ירוץ ירוץ וישאל שאלות, אבל בסופו של דבר הוא חייב לעצור ולענות “כן” או “לא”, הרי הוא בעל זמן ריצה פולינומי ובפרט חסום.

עכשיו נוכל לפרוש את כל השאלות הלא טריוויאליות שהאלגוריתם שאל במהלך הריצה:

\( c^{1}\cdot x\ne0 \)

\( c^{2}\cdot x\ne0 \)

\( \vdots \)

\( c^{m}\cdot x\ne0 \)

סה”כ \( m \) שאלות, כאשר \( m \) פולינומי ב-\( n \) (\( n \) הוא מספר האיברים ב-\( x \), כזכור). כעת אנחנו חושבים על \( x \) בתור וקטור של משתנים שהם מספרים שלמים, ועל השאלות של האלגוריתם בתור אי שוויונים, ואנחנו שואלים את עצמנו אם קיימת הצבת ערכים אפשרית ל-\( x \) שתספק את כל האי-שוויונים בו זמנית. יותר מכך - אנחנו רוצים שני פתרונות, \( x,y \) לאותה מערכת משוואות, אבל כך ש-\( x \) שייך ל-Subset-Sum ואילו \( y \) לא שייך. אם נוכיח שקיימים שני וקטורים כאלו, הרי שהוכחנו שהאלגוריתם טועה על אחד מהם, ובכך חיסלנו אותו. להוכיח פורמלית שקיימים שני פתרונות כאלו זה קצת טכני ולא אכנס לזה (היי, גם המאמר לא!) אבל אפשר להבין את הרעיון לא רע אם חושבים על הסיטואציה בדו-מימד, כלומר כאשר \( n=2 \): נוח לעבור לדבר על גיאומטריה ולכן אפשר לדבר על המרחב הוקטורי \( \mathbb{Q}^{2} \) (כל הנקודות הרציונליות במישור), ואז כל משוואה מהצורה \( c\cdot x=0 \) מגדיר ישר במרחב הזה. הפואנטה כעת היא שאיחוד סופי של ישרים לא יכול לכסות את כל המישור; השאלה אם נקודה במישור תכוסה על ידי אחד מהישרים זהה לשאלה אם היחס בין הקואורדינטות שלה שווה לשיפוע של אחד הישרים בקבוצה, אבל קבוצת השיפועים הזו סופית ויש אינסוף שיפועים אפשריים. זה מבטיח שאפשר למצוא פתרון למערכת האי-שוויונים ב-\( \mathbb{Q}^{2} \), ואפשר לעבור ממנו ל-\( \mathbb{Z}^{2} \) על ידי לקיחת הפתרון וכפל במכנה המשותף של הגורמים בו. שימו לב שבלי האינסופיות של \( \mathbb{Z} \) זה לא היה עובד.

האתגר הוא לוודא שאחד הפתרונות שייך ל-Subset-Sum. באופן כללי לא בטוח שנוכל למצוא פתרון כזה! למשל, נניח שלכל וקטור ב-\( \left\{ 0,1\right\} ^{n} \) שאינו וקטור האפס, יש שאלה \( c^{i} \) כלשהי שהאלגוריתם שאל ששווה לוקטור הזה (כלומר, האלגוריתם ביצע “חיפוש ממצה”) - ברור שלא נוכל למצוא פתרון \( x \) שמצד אחד עונה “לא שווה לאפס” על כל \( c^{i}\cdot x \) ומצד שני כן עונה \( a\cdot x=0 \) על \( a\in\left\{ 0,1\right\} ^{n} \) כלשהו.

כאן אנחנו חייבים להשתמש בכך שהאלגוריתם הוא פולינומי (שהרי כל מטרתו היא להוכיח ש-Subset-Sum שייכת ל-\( \mbox{P}_{\mathbb{Z}} \). זה אומר שקיים \( n \) גדול דיו כך שזמן הריצה הכולל של האלגוריתם יהיה לכל היותר \( 2^{n}-2 \) צעדים, כלומר בפרט \( m<2^{n}-1 \). זה מבטיח (שוב, נדרשת פה קצת עבודה טכנית) שיהיה \( a\in\left\{ 0,1\right\} ^{n} \) שלא “מכוסה” על ידי אף אחת מהשאלות של האלגוריתם, ולכן אפשר למצוא \( x \) כך ש-\( c^{i}\cdot x\ne0 \) לכל \( i \) אבל \( a\cdot x=0 \).

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