על P=NP מעל חבורות אבליות - סוף דבר

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

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

ובכן, נסמן ב-\( \mathbb{H}_{p} \) את הסכום הישר של \( \mathbb{Z}_{p} \), אז אני טוען ללא הוכחה ש-\( \mbox{P}_{\mathbb{H}_{p}}\ne\mbox{NP}_{\mathbb{H}_{p}} \), ושההוכחה דומה למקרה של \( \mathbb{Z} \). יפה. מה עכשיו?

עכשיו ניקח חבורה אבלית אינסופית כללית \( G \), ונבנה את העל-חזקה שלה ביחס לעל-מסנן שמתקבל ממסנן פרשה. כבר ראינו את הבניה הזו בדיוק בפוסט הקודם כשהיא מופעלת על המספרים הממשיים \( \mathbb{R} \), ואז היא יצרה לנו את המספרים ההיפר-ממשיים שבבסיס האנליזה הלא סטנדרטית. מה יקרה אם נעשה את זה עבור חבורה? ובכן, נקרא לעל-מכפלה שנקבל \( G^{*} \). לעל-מכפלה כזו יש את התכונה הקריטית לפיה כל פסוק בלוגיקה מסדר ראשון שהוא נכון עבור \( G \) נכון גם עבור \( G^{*} \) וההפך - זה נקרא שקילות אלמנטרית של שני המודלים הללו. עכשיו, מה שאנחנו רוצים להראות הוא שבעיית ה-Nullsack פתירה בזמן פולינומי מעל \( G \) אם ורק אם היא פתירה מעל \( G^{*} \), אבל איך אפשר להשתמש בשקילות האלמנטרית כדי להראות זאת? מה יהיה הפסוק שלנו? ובכן, כאן יש התחכמות קטנה - לכל \( n \) טבעי נבנה פסוק \( \psi_{n} \) שאומר, עבור אלגוריתם נתון, “האלגוריתם פותר נכון את Nullsack לכל הקלטים מאורך \( n \)”.

איך כותבים דבר כזה? ובכן, מנצלים את העובדה שזמן הריצה של האלגוריתם הזה חסום (בפרט חסום על ידי פולינום) ולכן עבור \( n \) נתון, מספר השאלות שהאלגוריתם עשוי לשאול הוא מוגבל וחסום על ידי קבוע. עכשיו כותבים פסוק מהצורה \( \psi_{n}=\forall x_{1},\dots x_{n}\left(\bigvee C_{k}\left(x_{1},\dots,x_{n}\right)\iff\exists a_{1}\dots a_{n}\in\left\{ 0,1\right\} \left(\sum a_{i}x_{i}=0\right)\right) \) כאשר כל \( C_{k} \) הוא תת-פסוק שמייצג מסלול חישוב מקבל אפשרי אחד של האלגוריתם. ממה מורכב מסלול חישוב כזה? ובכן, יש הרבה חישובים שהאלגוריתם עשוי לעשות “בצד”, אבל החישובים היחידים שמתייחסים לקלטים הם בדיקות מהצורה \( \vec{b}\cdot\vec{x}=0 \) שעליהן דיברנו בפוסט הקודם. סדרה נתונה של תשובות לשאלות הללו מגדירה מסלול חישוב, ולכן אפשר לכתוב \( C_{k}=l_{1}^{k}\wedge l_{2}^{k}\wedge\dots\wedge l_{t_{k}}^{k} \) כאשר כל \( l_{i}^{k} \) כזה מתאר את השאלה ה-\( i \) בחישוב, והוא יכול להיות עם סימן שלילה לפני כן (אם מסלול החישוב הספציפי מתאר את מה שקורה כשעל השאלה הזו עונים בשלילה).

כעת, אם קיים אלגוריתם שפותר את בעיית ה-Nullsack עבור \( G \), אז קיימים פסוקים \( \psi_{1},\psi_{2},\dots \) שמתארים את הריצה שלו על קלטים מכל גודל אפשרי, כך ש-\( G\models\psi_{n} \) לכל \( n \), ולכן \( G^{*}\models\psi_{n} \) לכל \( n \) ולכן אותו אלגוריתם בדיוק עובד גם על \( G^{*} \), למרות שב-\( G^{*} \) יכולים להיות קלטים מסובכים הרבה יותר. הנה לכם טעימה מהכוח של תורת המודלים. כל מה שנשאר לנו לעשות הוא להוכיח שלא יכול להיות קיים אלגוריתם פולינומי שפותר את Nullsack עבור \( G^{*} \), וכדי להראות את זה, מספיק להראות שיש ב-\( G^{*} \) תת-קבוצה \( H \) שעבורה בעיית ה-Nullsack לא פתירה, כי אם יש כזו, ויש אלגוריתם שפותר Nullsack על כל \( G^{*} \), פשוט נפעיל אותו על קלטים שמגיעים מ-\( H \) (ומה על קלטים שלא שייכים ל-\( H \)? ובכן, כשאנחנו מדברים על בעיית ה-Nullsack מעל \( H \), אנחנו מראש פוסלים קלטים כאלו - הקלטים היחידים שיכולים להגיע הם קלטים מתוך \( H \)).

לכן על מנת לסיים את ההוכחה, מספיק יהיה להראות שיש ב-\( G^{*} \) עותק של \( \mathbb{Z} \) או עותק של \( \mathbb{H}_{p} \) עבור \( p \) מסויים. ולמה זה נכון?

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

אם ב-\( G \) יש איבר מסדר אינסופי, אז החזקות שלו לבדן יוצרות עותק איזומורפי של \( \mathbb{Z} \) ולכן סיימנו. אחרת, כל האיברים ב-\( G \) הם מסדר סופי, אבל עדיין יש שני מקרים אפשריים: או שקבוצת הסדרים היא לא חסומה (כלומר, לכל \( n \) טבעי יהיה איבר שהסדר שלו הוא לפחות \( n \)) או שהיא חסומה. אם היא לא חסומה, בואו נסתכל על האיבר הבא של \( G^{*} \): \( g=\left(g_{1},g_{2},g_{3},\dots\right) \) כך שהסדר של \( g_{1} \) קטן ממש מהסדר של \( g_{2} \) שקטן ממש מהסדר של \( g_{3} \) וכן הלאה. כעת, הנוסחה “הסדר של \( g \) הוא לכל הפחות \( n \)” יכולה להיות שגויה רק עבור מספר סופי של קואורדינטות ב-\( g \), ולכן קבוצת הקואורדינטות ב-\( G \) שעבורן הנוסחה נכונה היא קו-סופית, ולכן שייכת לעל-מסנן שהגדיר את \( G^{*} \), כך ש-\( g \) מקיים את הנוסחה הזו, וזאת לכל \( n \). מסקנה: הסדר של \( g \) גדול מכל \( n \) טבעי, ולכן הוא אינסופי, והנה שוב מצאנו איבר מסדר אינסופי שיוצר תת-חבורה איזומורפית ל-\( \mathbb{Z} \) וסיימנו.

נשאר רק לטפל במקרה שבו יש רק מספר סופי של סדרים אפשריים לאיברים ב-\( G \). כעת אני רוצה להכניס לתמונה מושג סטנדרטי מתורת החבורות - אקספוננט של חבורה. האקספוננט של חבורה \( G \) הוא המספר הטבעי המינימלי \( n \) כך שכל איבר ב-\( G \) מחזיר את היחידה כאשר מעלים אותו בחזקה \( n \), דהיינו \( \mbox{exp}G=\min_{n}\left\{ \forall g\in G:g^{n}=e\right\} \). בחבורה סופית, \( \left|G\right| \) הוא תמיד מועמד טוב להיות אקספוננט כי הוא מקיים את התכונה הזו ולכן לכל היותר האקספוננט יהיה מספר קטן יותר שמחלק אותו; אבל בחבורה אינסופית ייתכן שהאקספוננט בכלל לא יהיה קיים. למשל, ב-\( \mathbb{Z} \) אין אקספוננט. במקרה הזה נוח להגיד שהאקספוננט הוא “אינסוף”.

אם ב-\( G \) יש רק מספר סופי של סדרים לאיברים, ודאי שיש לה אקספוננט סופי, כי למשל המכפלה של כל הסדרים האפשריים של איברים היא מספר שמועמד להיות האקספוננט, כמו \( \left|G\right| \) בחבורה סופית. כעת אני יכול לשלוף את הג’וקר שלי מהשרוול - משפט (לא טריוויאלי) בתורת החבורות של Prüfer שאומר שחבורה אבלית סופית מאקספוננט סופי היא בהכרח סכום ישר של חבורות מהצורה \( \mathbb{Z}_{p} \), כאשר \( p \) הוא ראשוני (אבל יכולות להיות בסכום חבורות שונות עם ראשוניים שונים). די ברור שמספר הראשוניים השונים הרלוונטיים חייב להיות סופי, אחרת היינו מסוגלים למצוא איברים מסדרים גדולים כרצוננו (כי ב-\( \mathbb{Z}_{p} \) יש איבר מסדר \( p \)). כמו כן, סכום של מספר סופי של חבורות מהצורה \( \mathbb{Z}_{p} \) הוא חבורה סופית, ולכן מכיוון ש-\( G \) אינסופית, הסכום חייב להיות של מספר אינסופי של מחוברים. המסקנה היא שיש \( p \) כך ש-\( G \) ניתנת לתיאור כסכום ישר של משהו ועוד אינסוף עותקים של \( \mathbb{Z}_{p} \), או במילים אחרות - \( G \) מכילה את \( \mathbb{H}_{p} \) כתת-חבורה, וזה מסיים את ההוכחה. הבטחתי שילוב של סיבוכיות, תורת המודלים ותורת החבורות? הנה תורת החבורות צצה לה ברגע האחרון (ואני מקווה שגם מי שיש לו היכרות בסיסית עם תורת החבורות למד עכשיו על קיומו של משפט חדש).