אז מה בין קודים לתיקון שגיאות והוכחת משפט ה-PCP?

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

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

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

על מעגלים בוליאניים אפשר לכתוב פוסטים מכאן ועד להודעה חדשה, אבל כמו במקרה של קודים לתיקון שגיאות גם כאן אתמקד כעת במה שרלוונטי עבורנו. בבסיסם, מעגלים הם מודל חישובי פשוט מאוד, שמורכב מ”שערים לוגיים” וחיבורים ביניהם. שער לוגי מקבל מספר ערכים, שכל אחד מהם הוא או 0 או 1, ומבצע עליהם חישוב פשוט. למשל, שער NOT מחזיר 1 אם קיבל 0, ו-0 אם קיבל 1; ושער AND מקבל שני ערכים, מחזיר 1 אם שניהם 1 ואחרת (אם לפחות אחד מהם הוא אפס) מחזיר 0. יש עוד שערים אבל די לנו בשני אלו כדי לייצג כל פונקציה בוליאנית (פונקציה שמקבלת מספר ערכים של 0 ו-1 ומחזירה כפלט 0 או 1) בעזרת מעגל שמכיל רק את השערים הללו.

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

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

נתמקד כעת במקרה שלנו - אנחנו מדברים על בעיות שנמצאות ב-NP, כלומר בעיות שאפשר לנסח במונחים של “וידוא שמילה \( w \) שייכת לשפה \( L \)”, כך שקיים “מוודא” עבור השפה \( L \) שמסוגל לקרוא “הוכחות” \( \pi \) לכך ש-\( w\in L \) ולומר “כן”, ואם \( w\notin L \) אז שום הוכחה לא תגרום למוודא לומר כן; והמוודא מבצע את הבדיקה שלו ביעילות - זמן שהוא פולינומי בגודל של \( w \). את המודל הזה אפשר להחליף במודל של מעגלים - לכל מספר טבעי \( n \) אפשר לבנות מעגל כך שהוא מקבל קלט \( w \) מאורך \( n \), ועוד קלט \( \pi \) מאורך כלשהו שפולינומי ב-\( n \) (וגם הוא קבוע), כך שאם \( w\in L \) אז קיים \( \pi \) שעבורו המעגל פולט 1, אם \( w\notin L \) אז לכל \( \pi \) המעגל פולט 0, וגודל המעגל כולו פולינומי ב-\( n \) (כלומר, אין מספר גדול במיוחד של שערים). איך אפשר לבנות מעגל כזה? שאלה מצויינת. למי שמכיר את משפט קוק-לוין, הרעיון זהה (משפט קוק-לוין מתוחכם עוד יותר - מסמלצים מכונת טיורינג באמצעות נוסחה בתחשיב הפסוקים - ועל נוסחה כזו אפשר לחשוב כגרסה פשוטה של מעגל בוליאני, שבו כל יציאה של שער נכנסת לכניסה של שער אחד בלבד, כלומר לא ניתן “למחזר” אותה). למי שלא מכיר - תאמינו לי לבינתיים, זו לא מטרת הפוסט.

עכשיו בואו נסתכל על התמונה הגדולה. נניח שאני מוודא PCP עבור השפה \( L \). בהינתן מילה \( w \), אני מצפה לקבל הוכחה כלשהי לכך ש-\( w \) שייכת ל-\( L \) - הוכחה שאצטרך לדגום ממנה רק מספר קבוע של ביטים. איך תיראה ההוכחה הזו? בתור התחלה, נוכל לחשוב על המעגל שתיארתי קודם, שמסמלץ את מוודא ה-NP עבור \( L \); אפשר “להקפיא” את הכניסות שמייצגות את \( w \), ולכן נישאר עם מעגל שאסמן ב-\( C \), שמקבל קלט בודד - \( \pi \) - וקיים פלט כלשהו שעבורו הוא פולט 1 רק אם \( w \) שייך לשפה. כלומר, כדי להשתכנע ש-\( w\in L \) אני רוצה שיביאו לי הוכחה שניתן לספק את \( C \).

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

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

הצעד הבא הוא להסכים לקבל הוכחה מהסוג שתיארתי כרגע, של “רשימת כל הערכים שהשערים של \( C \) מקבלים שמזינים ל-\( C \) \( \pi \) שמספק אותו”, אבל לא לקרוא את כולה, אלא רק “לדגום” חלקים ממנה. מה בעצם אנחנו רוצים לבדוק? ששער היציאה של \( C \) הוא 1 (אחרת \( \pi \) בוודאי שאינו מספק את \( C \)) ושכל שער מתנהג בצורה חוקית. אם נמספר את כל השערים ב-\( C \) ונסמן ב-\( \alpha_{i} \) את הערך של השער ה-\( i \) (נניח לצורך העניין שגם הביטים של \( \pi \) מיוצגים על ידי שערים), אפשר לסכם את הדרישות באופן הבא:

1. \( \alpha_{t}=1 \), כאשר \( t \) הוא מספר שער היציאה של \( C \).
2. אם \( i \) הוא שער AND שהכניסות שלו הן מהשערים \( j,k \), אז \( \alpha_{i}=\alpha_{j}\alpha_{k} \).
3. אם \( i \) הוא שער NOT שהכניסה שלו היא מהשער \( j \), אז \( \alpha_{i}=\alpha_{j}+1 \) (כאן חיבור הוא מודולו 2, כלומר \( 1+1=0 \)).

אם כן, צמצמנו את ה”הוכחה” שאנחנו רוצים לקבל לאוסף של ביטים \( \alpha_{i} \) שמקיימים אוסף של “אילוצים”. כשבודקים את \( C \) אפשר לבחור באופן אקראי אחד מהאילוצים, נניח אילוץ AND שמערב את שערים \( 5,3,1 \) ולבדוק אם \( \alpha_{5}=\alpha_{3}\alpha_{1} \) - דבר שדורש קריאה של שלושה ביטים בלבד. אם כן - נניח שהכל בסדר ונגיד “כן”, ואם לא, נדחה. הכוח שלנו נובע מכך שכל אחד מהאילוצים עלול להיות מוגרל, ולכן מי שמספק לנו את ההוכחה לא יכול לרמות באף אחד מהם.האמנם?

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

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

בואו נלך עוד צעד אחד קדימה בדרך לפישוט הבעיה שלנו. לכל אילוץ אפשרי נגדיר משתנה \( \phi_{i} \), שמקבל את הערך 0 אם האילוץ מסופק ואת הערך 1 אם הוא מופר. למשל, \( \phi_{t}=1+\alpha_{t} \); ואם \( i \) הוא שער AND אז \( \phi_{i}=\alpha_{i}+\alpha_{j}\alpha_{k} \); ואם \( i \) הוא שאר NOT אז \( \phi_{i}=\alpha_{i}+\alpha_{j}+1 \). כעת, מהו הסכום \( \sum\phi_{i} \) (מודולו 2)? אם כל האילוצים מסופקים, יש לנו סכום של אפסים, ולכן הסכום יהיה אפס; ואילו אם אילוץ אחד לפחות מופר, הסכום יהיה שונה מאפס… רגע, אופס, לא. בגלל שהסכום הוא מודולו 2, אז הסכום יהיה שונה מאפס אם מספר אי זוגי של אילוצים מופר, אבל יהיה עדיין אפס אם מספר זוגי של אילוצים מופר.

אז בואו נשכלל עוד יותר את הבדיקה. במקום לסכום את כל האילוצים, מה שנעשה יהיה להגריל תת קבוצה של אילוצים; עבור כל אילוץ נטיל מטבע, ובהסתברות של \( \frac{1}{2} \) נוסיף אותו לסכום. כלומר, בסופו של דבר נחשב צירוף לינארי \( \sum a_{i}\phi_{i} \), כאשר \( a_{i} \) שווה או לאפס (בהסתברות חצי) או לאחד (בהסתברות חצי). אם אף אילוץ לא מופר, הסכום של כל צירוף לינארי שכזה יהיה 0; אם לפחות אילוץ אחד מופר, כמה מהצירופים הללו יהיו שווים ל-1?

כאן נכנס לתמונה תעלול נפוץ בניתוח של סיטואציות מעין אלו. הבה ניקח אילוץ ספציפי אחד שמופר, \( \phi_{j}=1 \), ו”נקפיא” אותו. כעת, אפשר לחלק את כל הצירופים הלינאריים האפשריים לשני סוגים - כאלו שבהן \( a_{j}=0 \), וכאלו שבהם \( a_{j}=1 \). הבה וניקח צירוף לינארי שכזה שבו \( a_{j}=0 \), כלומר \( \phi_{j} \) לא משתתף בו. אם סכומו של הצירוף הזה הוא 0, אז ערכו של הצירוף שזהה לו בכל פרט לכך ש-\( a_{j}=1 \) יהיה 1 (שכן הוספנו לצירוף הזה, שקודם ערכו היה 0, את הערך \( \phi_{j} \) שהוא 1). בדומה, אם סכומו של הצירוף היה 1, אחרי שנשנה את \( a_{j} \) ל-1 נקבל 0.

מה זה בעצם אומר? שאפשר לפרק את קבוצת כל הצירופים הלינאריים לאוסף של זוגות, כך שבכל זוג בדיוק אחד משני הצירופים נותן 1, והצירוף השני נותן 0. מסקנה: אם ולו אילוץ אחד מופר, הרי שבדיוק חצי מהצירופים האפשריים נותן 1. לכן אם באמת נגריל את הצירופים באופן שתיארתי לעיל (כל אילוץ נבחר בהסתברות חצי) תהיה לנו הסתברות חצי לגלות שעבדו עלינו, בלי תלות בגודל המעגל. אאורקה!

כל זה טוב ויפה, אבל עדיין לא הסברתי איך אפשר, אחרי שכבר הגרלתי צירוף לינארי מסויים \( \sum a_{i}\phi_{i} \), לחשב את ערכו על ידי קריאה של ביט אחד בלבד. לשם כך צריך להיזכר מהם \( \phi_{i} \) השונים. בואו נשכח לרגע מכך ש-\( \phi_{i} \) יכול להכיל דברים שנראים כמו \( \alpha_{j}\alpha_{k} \) (כלומר, מכפלה של שתי \( \alpha \)-ות) ונדמיין, אם כן, שכל צירוף \( \sum a_{i}\phi_{i} \) ניתן לתיאור באמצעות צירוף מהצורה \( \sum b_{i}\alpha_{i}+b \) כש-\( b \) הוא קבוע. כלומר, כדי לחשב את \( \sum a_{i}\phi_{i} \) מספיק להיות מסוגלים לחשב את \( \sum b_{i}\alpha_{i} \) - לחשב צירוף לינארי של ה-\( \alpha \)-ות ששייכות להוכחה שקיבלנו. לרוע המזל, נראה שלא הרווחנו כלום - כדי לחשב צירוף כזה צריך לקרוא במפורש את כל ה-\( \alpha_{i} \)-ות שעבורן \( b_{i}\ne0 \), אז מה יצא לנו מזה?

כאן נכנס לתמונה קוד הדמר שתיארתי בפוסט הקודם. כזכור, קוד הדמר של מילה היה מורכב מכל הצירופים הלינאריים האפשריים של הביטים במילה. אם כן, אם מישהו נותן לנו בתור הוכחה לא את ה-\( \alpha_{i} \) אלא את קידוד הדמר שלהן - ניצחנו, כי אז כדי לחשב את \( \sum b_{i}\alpha_{i} \) די בדגימת הביט הבודד מתוך קוד הדמר שמכיל את הצירוף הלינארי הזה. אם כן, האם סיימנו?

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

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

נסכם: לקחנו את הבעיה של הוכחה ש-\( w\in L \) וצמצמנו אותה לבעיה של הוכחה שמעגל \( C \) כלשהו ספיק. ה”הוכחה” לכך היא תיאור של השמה מספקת ל-\( C \) והערכים ששערי \( C \) מקבלים כשמזינים אותה אליו, כשכל זה מקודד בקוד הדמר. בהינתן ההוכחה הזו, אנחנו:

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

סוף דבר.או שלא. הסתרתי כאן עוד קושי טכני מרגיז - ה-\( \phi_{i} \) יכול להכיל גם איברים מהצורה \( \alpha_{i}\alpha_{j} \), כלומר ב”צירוף הלינארי” שעלינו לחשב עשויים להופיע גם איברים מהצורה \( b\alpha_{i}\alpha_{j} \), מה שאומר שזה בכלל לא צירוף לינארי אלא צירוף “ריבועי”. איך פותרים את זה? ובכן, זה טכני, ולא משנה שום דבר מהותי ברעיונות של ההוכחה, ולכן לא אתעמק בכך; הרעיון הוא להגדיר משתנים חדשים, \( \beta_{ij}=\alpha_{i}\alpha_{j} \), ואז לדבר על צירופים לינאריים של ה-\( \beta \)-ות הללו. זה מגדיל עוד קצת את מספר הבדיקות שעלינו לעשות, אך הוא עדיין יהיה קבוע.

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