ארכיון חודשי: יולי 2007

שורש, ההוכחה (חלק א’)

פורסם בתאריך על ידי
5

אם השעה היא 19:00 ושואלים אותנו מה תהיה השעה עוד שש שעות, אנו עונים שהיא תהיה 1:00. איך אנחנו יודעים? אנחנו מחברים 6 ל-19, מקבלים 25, ומחסרים 24 מהתוצאה, כי הרי בשעון, כל 24 שעות "מתחילים מהתחלה".

זו דוגמה לאריתמטיקה מודולרית – במקרה הזה, אריתמטיקה מודולו 24. המשמעות היא פשוטה: האיברים שלנו הם מספרים שלמים בתחום מ-0 עד 23, ופעולות החשבון הבסיסיות (חיבור וכפל) מתבצעות כרגיל, פרט לכך שאחרי סיומן אנו מחלקים את התוצאה ב-24 ולוקחים רק את השארית. אלו מכם שיש להם נסיון בתכנות ודאי מכירים אופרטור שמצוי ברוב השפות הקיימות (ב-++C ושפות בעל תחביר דומה הוא "%") שמבצע פעולת חילוק-ולקיחת-שארית שכזו. כך למשל באריתמטיקת השעון שלנו מתקיים \(5\cdot 7=11\) כי את התוצאה במספרים "רגילים", 35, אנו מחלקים ב-24 ולוקחים שארית. עוד מתקיים גם \(3\cdot 8=0\), כי כאן התוצאה היא 24, והשארית על כן היא 0.

כמובן, כל הניסוח ה"אלגוריתמי" הזה מרגיש לא פורמלי למדי, ויש הגדרות טובות יותר למבנה הזה, של מספרים מודולו n. הרעיון הבסיסי הוא לחשוב עליהם כעל מחלקות שקילות של המספרים השלמים, כשיחס השקילות הוא "ל-\(x\) ול-\(y\) אותה שארית בחלוקה ב-\(n\)" – ובניסוח אפילו יותר מדוייק, \(n\) מחלק את \(x-y\)". לאחר מכן מוגדרות פעולות הכפל והחיבור על נציגים של מחלקות השקילות, ומתברר שהכל יוצא מוגדר היטב.

מה באשר לשאר פעולות החשבון הבסיסיות? חיסור לא מציב שום בעיה, כל עוד מוכנים לבצע מציאת שארית בצורה קצת שונה מזו שהמחשב עושה: כך למשל ה"שארית" של מינוס 2 באריתמטיקה מודולו 24 היא 22 דווקא (כי זה המספר היחיד בטווח מ-0 ועד 23 שהמרחק שלו ממינוס 2 הוא כפולה שלמה של 24). חילוק, לעומתו, זה סיפור שונה לגמרי.

ברור שחילוק "רגיל" לא עוזר לנו. כך למשל \(7/2=3.5\) היא לא תוצאה קבילה, כי \(3.5\) הוא לא מספר שלם בין 0 ל-23. לכן עלינו לשאול את עצמנו ראשית כל מה אנו רוצים.

חילוק, באופן כללי, הוא הפעולה ההפוכה לכפל. כלומר, \(a/b=x\) פירושו שמתקיים \(b\cdot x=a\). תוצאת החלוקה של \(a\) ב-\(b\) היא המספר שכאשר כופלים אותו ב-\(b\) מקבלים את \(a\). בפועל, קל להראות (נסו!) שמספר זה הוא בדיוק המספר אשר מתקבל כאשר כופלים את \(a\) בהופכי הכפלי של \(b\) – כלומר, במספר \(t\) כלשהו (אני נמנע בכוונה מהסימון המקובל) שעבורו מתקיים \(b\cdot t=1\).

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

כאשר עוסקים במספרים ממשיים, אפס הוא המספר הבעייתי היחידי. לעומת זאת, באריתמטיקה מודולו n, יכולים להיות מספרים בעייתיים נוספים. אפשר להראות (שוב, ללא קושי רב – נסו!) שכל זוג מספרים שונים מאפס המקיימים \(a\cdot b=0\) (מספרים כאלו נקראים מחלקי אפס, וכבר הזכרתי אותם בעבר) אינם הפיכים. עם עוד קצת מאמץ אפשר לראות שמספר שהוא זר ל-\(n\) (כלומר, אין מספר פרט ל-1 שמחלק גם אותו וגם את \(n\)) הוא הפיך, ואילו מספר שאינו זר ל-\(n\) הוא מחלק אפס, ולכן אינו הפיך. נסו להוכיח זאת. (רמז: אם מספר \(a\) הוא זר ל-\(n\) אז קיימים \(x,y\) שלמים כך ש-\(xa+yn=1\); אם מספר לא זר ל-\(n\) אז קיים מספר קטן ממש מ-\(n\) שמחלק גם אותו וגם את \(n\)).

אם \(n\) הוא מספר ראשוני, הכל טוב ויפה: במקרה זה, כל מספר בין 1 ל-\(n-1\) הוא זר ל-\(n\), ולכן כל המספרים הפיכים – ואכן, המבנה האלגברי שמתקבל הוא שדה (כמו הרציונליים והממשיים). למעשה, השדות הללו חשובים מאוד: במובן מסויים, כל השדות ממציין שאינו 0 בנויים "מעל" השדות הללו (הזכרתי את מושג המציין בפוסט קודם – זה המספר הקטן ביותר של פעמים שיש לחבר את 1 לעצמו כדי לקבל 0, ומציין 0 פירושו שזה בלתי אפשרי).

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

סיימנו עם ארבע פעולות החשבון הבסיסיות. הפעולה הבאה בתור היא הוצאת שורש. שוב, שורש כאן אינו שורש במובן הרגיל, של "שורש 2 הוא \(1.41421356\dots\)", אלא במובן של "איבר בחבורה שכשמכפילים אותו בעצמו מקבלים את 2". למשל, בחבורת אוילר מסדר 7, המספר 3 הוא (באופן מפתיע?) שורש של 2: 3 כפול עצמו זה 9, ומודולו 7 מקבלים 2. באופן דומה גם 4 הוא שורש.

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

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

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

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

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

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

פורסם בתאריך על ידי
2

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

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

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

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

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

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

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

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

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

חשוב לציין שוב – מושג הסימולטור הוא מושג קשה ומורכב יחסית, ולא הצגתי אותו כאן בצורה מדוייקת כלל. המטרה שלי היא בעיקר לתת "תחושה" של המושג (וככל הנראה, זוהי בעיקר תחושתי הסובייקטיבית), ולכן יש לנהוג במשנה זהירות.

בואו נעבור להדגמה של סימולטורים לשני הפרוטוקולים שכבר ראינו: זה של איפה אפי, וזה של ה-3-צביעה.

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

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

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

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

מוכיחים את הלא נודע

פורסם בתאריך על ידי
6

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

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

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

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

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

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

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

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

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

"איפה אפי" ("Where's Waldo" באנגלית) הוא גיבורה של סדרת ספרים שכל אחד מהם מורכב מתמונות רבות עמוסות באנשים, שבכל אחת מהן יש לאתר את אפי בתוך הקהל. אני אישית מעדיף את "ספר עולמי" וספרי "1000 מילים ראשונות" שיצאו בהוצאת מסדה פרס וא. קלין (מה קרה לספרים? מה קרה להוצאות? מתי יוציאו עוד ספרים כאלו?) שגם בהם היה צריך לחפש מישהו – כלב במקרה של ספר עולמי, ברווז וצפרדע במקרה של 1000 מילים ראשונות.

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

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

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

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

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

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

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

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

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

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

  1. אם באמת הצביעה שלנו הייתה חוקית, הרי ששני הצמתים יהיו צבועים בצבעים שונים. בגלל שהגרלנו פרמוטציה על צבעי הצמתים, זה גם כל המידע שהמוודא יפיק – ששני הצמתים הללו צבועים בצבע שונה (וזה מידע שממילא יש לו כי כל שני צמתים המחוברים בקשת צריכים להיות צבועים בצבע שונה).
  2. אם הצביעה שלנו אינה חוקית, אז יש שני צמתים שמחוברים בקשת שצבועים באותו הצבע. אם המוודא יבחר אותם באקראי, הלך עלינו. הסיכוי שהמוודא יבחר אותם הוא \(1/k\), כאשר \(k\) הוא מספר הקשתות.

אם כן, התנאים מתקיימים. אמנם, נראה כי הסתברות של \(1/k\) לגלות שקר היא עלובה למדי – אבל כמקודם, אם חוזרים על הפרוטוקול מספיק פעמים (כש"מספיק" פירושו "ממש לא הרבה ביחס לזמן שיקח לנו לבדוק את כל הצביעות האפשריות בעצמנו"), ההסתברות לטעות היא אפסית.

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

3-צביעה - הוכחה באפס ידע

התשובה היא שממש לא. ייתכן שבסיבוב הראשון הפרמוטציה שהגריל המוכיח הייתה "אדום->אדום, צהוב->צהוב, ירוק->ירוק" ובשני הייתה "אדום->אדום, צהוב->ירוק, ירוק->צהוב" ואז ב' צבוע במקור בצהוב, וג' בירוק והם שונים; אבל ייתכן שבסיבוב השני הוגרלה אותה פרמוטציה כמו בראשון, ואז ב' וג' שניהם צבועים במקור בצהוב והם זהים. בקיצור – המוודא לא לומד כלום, כי כל האפשרויות לצביעה אפשריות – פרט לאפשרות של "שני צמתים מחוברים בקשת צבועים באותו הצבע" (שאלת אתגר: למה המוודא חייב לבחור רק צמתים מחוברים בקשת? מה יקרה אם הוא יוכל לבקש מהמוכיח לחשוף גם צמתים שאינם מחוברים בקשת?).

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

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

עימות המוכיחים

פורסם בתאריך על ידי
5

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

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

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

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

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

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

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

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

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

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

גרפים
לבדוק האם שני גרפים הם איזומורפיים זה לא קל (כי יש המון דרכים שונות לשינוי שמות הצמתים), אבל להוכיח זאת זה קל: בתור הוכחה פשוט נותנים את ההתאמה הדרושה ("צומת a הופך לצומת 3, צומת b הופך לצומת 6…"). אבל איך אפשר להוכיח ששני גרפים אינם איזומורפיים? על פניו זה קשה מאוד – צריך להראות שלכל שינוי שמות של הצמתים בגרף האחד לא ניתן לקבל את הגרף השני.

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

  1. המוודא בוחר באקראי את אחד משני הגרפים, משנה את שמות הצמתים שלו בצורה אקראית, ושולח אותו למוכיח.
  2. המוכיח אומר למוודא לאיזה משני הגרפים המקוריים הגרף שהמוודא שלח לו איזומורפי.
  3. אם המוכיח צדק, ממשיכים לסיבוב הבא, אלא אם המוודא כבר השתכנע. אם המוכיח טעה, המוודא מעיף אותו מכל המדרגות.

זהו!

מה הולך כאן?

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

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

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

אם כן, המוודא מגלה שקר בהסתברות של \(\frac{1}{2}\). זה נשמע איום ונורא, אבל זה פחות גרוע ממה שניתן לשער, מכיוון שהמוודא יכול לחזור על הפרוטוקול שוב ושוב ושוב עד אשר ישתכנע. מכיוון שכדי שיצליחו לעבוד עליו, הניחוש של המוכיח צריך להצליח בכל אחד מהסיבובים, ההסתברות שהמוודא יטעה אחרי \(n\) סיבובים היא \(\frac{1}{2^n}\) – וכבר עבור ערכים קטנים של \(n\) – למשל, 20 – ההסתברות הזו היא אפסית. נמוכה בהרבה מההסתברות שאם מרצה יגיד על שקר כלשהו "תאמינו לי", הסטודנטים יקבלו את דבריו בלי היסוס (טוב, על מי אני עובד? ההסתברות לכך גדולה מ-50%!).

אז הכל טוב ויפה, אבל איפה נכנס אפס-הידע לעניין? על כן – בפעם הבאה.

מוכיח בשער

פורסם בתאריך על ידי
5

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

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

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

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

טוב, ברור שהמרכאות סביב "ישתכנע" הכרחיות כאן, כי הוכחה שכזו מבטיחה שהמוודא לא ישתכנע בכלל (למרות שלמוכיח הוא כנראה יגיד שהוא משוכנע). אבל אולי בכל זאת, גם בלי אלימות, המוכיח יהיה מסוגל לעבוד על המוודא ו"להוכיח" טענה שאיננה נכונה?

התשובה היא שזה תלוי במערכת ההוכחה שלנו. אנחנו יכולים לעצב את מערכת ההוכחה שלנו בצורה כזו שתמנע רמאויות שכאלו כל עוד המוודא פועל לפי הנחיות מוגדרות היטב לבדיקת ההוכחה שהמוכיח מספק לו – במילים אחרות, יש למוודא אלגוריתם לפעולה. מכיוון שמסובך לתת אלגוריתם לבדיקת טענות כלליות, הדיון מתמקד רק בדברים שניתן לנסח בפורמליזם מדוייק – ובפרט, אדבר כאן רק על שאלות "כן/לא" הנוגעות לאובייקטיים שניתנים לייצוג דיגיטלי (למשל: "האם המספר 5235432 הוא ראשוני?").

על פניו, נראה שהוכחות מתמטיות "רגילות" מהוות מקרה פרטי של הוכחות "אלגוריתמיות" שכאלו: אם קיימת הוכחה מתמטית לטענה ואנחנו רוצים להוכיח אותה אלגוריתמית, פשוט ניתן עותק כתוב של ההוכחה למוודא, ושישבור את הראש על זה. הרעיון הבסיסי נכון; עם זאת, החלק של "לשבור את הראש" הוא הבעייתי. מה שהמוודא צריך הוא דרך אלגוריתמית לבדוק, בהינתן טענה שכתובה לידה "אקסיומה", שהטענה הזו היא אכן אחת מהאקסיומות של התורה שלנו (מה שיכול להיות קשה או בלתי אפשרי עבור מערכות הוכחה שיש בהן מספר אינסופי של אקסיומות – ורוב מערכות ההוכחה הן כאלו), וכמובן שאם הוא רואה טענה שכתוב לידה "נובע מטענות 3 ו-5 וכללי היסק א' ו-ג'" הוא צריך דרך אלגוריתמית לבדוק שאכן הטענה נובעת מהטענות הקודמות ומכללי ההיסק.

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

הנה דוגמה למערכת הוכחה, במקרה הזה מערכת שתפקידה להוכיח שמספר כלשהו \(b\) אינו ראשוני. ה"פרוטוקול" שמתבצע כאן הוא פשוט: המוכיח מביא למוודא מספר שונה מ-1 ומ-\(b\) שמחלק את \(b\). המוודא מחלק את \(b\) במספר שהמוכיח נתן לו ובודק האם התקבלה שארית. אם לא התקבלה, המוודא משתכנע בנכונות ההוכחה – כלומר, ש-\(b\) הוא אכן אינו ראשוני. אם התקבלה שארית (או אם המספר שנשלח בהתחלה היה \(b\) או 1), הוא צועק על המוכיח שהוא שקרן עלוב ובועט אותו מכל המדרגות.

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

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

נאותות פירושה שלא מסוגלים "לעבוד" עלינו – שאי אפשר יהיה להוכיח דברים שאינם נכונים. ברמה המחמירה ביותר הדרישה הזו היא מוחלטת, אבל מתברר שהחלשתה (כלומר, התרת האפשרות שיעבדו עלינו, אף אם בהסתברות אפסית שאנו מסוגלים לשלוט על גודלה) היא זו שמביאה אותנו לחלקים המעניינים באמת של מערכות ההוכחה, וארחיב על כך בהמשך. במקרה שלנו הנאותות של המערכת היא מוחלטת: אם יש לנו מספר ראשוני \(b\), אז לא משנה איזה מספר נשלח למוודא, הוא יסרב להשתכנע בנכונות ההוכחה שלנו – כי לא משנה איזה מספר נשלח למוודא, כל עוד הוא אינו \(b\) או 1, הוא לא יחלק את \(b\) בלי שארית ולכן דעתו של המוודא לא תפוייס.

מה שבעייתי במערכת שלנו הוא שהמוכיח נראה בה כמעט מיותר. אם יש מספר \(b\) ואני רוצה להשתכנע שהוא אינו ראשוני, אני פשוט אנסה לחלק אותו בכל המספרים הקטנים ממנו (ויש שיאמרו – עד השורש שלו ולא למעלה מכך) ואם אמצא מישהו שמחלק אותו בלי שארית, גמרתי (ואם לא – לא). מה ההבדל הגדול?

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

כמובן שאפשר להתלונן "ואיך המוכיח מצא את המחלק?" וזה יהיה לגיטימי. ההנחה המקובלת במערכות הוכחה היא שהמוכיח הוא "כל יכול", במובן זה שהוא מסוגל לחשב הכל ובקלות, ואילו המוודא הוא זה שמוגבל מבחינה חישובית. ההנחה הזו אינה מופרכת לגמרי; לפעמים ישנן בעיות שקל "להמציא" מרגע שפתרונן כבר ידוע. למשל, בדוגמת המספר והמחלקים שלנו, אם אני המוכיח אני יכול לבחור באקראי שני מספרים גדולים \(x,y\), לכפול אותם ולקבל מספר מפלצתי בגודלו, \(xy\). כעת, המוודא יכול לשבור את הראש על המספר הזה במשך זמן רב, ואילו אני בתור המוכיח כבר מכיר מחלק עבורו – \(x\). רעיון דומה לזה ניצב בבסיס שיטת ההצפנה RSA – ובמובן מסויים, גם בבסיס כל שיטות ההצפנה המודרניות האחרות. אם כן, הכוח הרב של המוכיח לא תמיד נובע מכך שיש לו מחשב על זמין; לפעמים מספיק שיהיה לו ידע ספציפי על הבעיה שאין למוודא. נחזור לכך בהמשך, כשנעסוק בהוכחות אפס-ידע.

בפעם הבאה – איך האינטראקטיביות נכנסת לסיפור.

בסיס מוצק מי ימצא

פורסם בתאריך על ידי
13

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

עבור מרחב ממימד סופי המשפט טריוויאלי, והטכניקה פשוטה: לוקחים איבר \(a_1\). מחפשים איבר נוסף במרחב שאינו תלוי לינארית ב-\(a_1\). אם אין כזה – מה טוב, \(\{a_1\}\) הוא בסיס למרחב. אחרת, יש איבר \(a_2\) שכזה, ולכן נוסיף אותו לקבוצת ה"בסיס הפוטנציאלי" שלנו, ונמשיך הלאה. מכיוון שאנחנו במרחב ממימד סופי, יש חסם על גודל הקבוצה הבלתי תלויה המקסימלית, ולכן התהליך יהיה חייב לעצור – כלומר, נגיע לאיזו קבוצה \(\{a_1, a_2,\dots, a_n\}\) שכל איבר במרחב תלוי לינארית בה – כלומר, ניתן לכתיבה כצירוף לינארי של איבריה, וזהו. באותה צורה אפשר להרחיב כל קבוצה בלתי תלויה לבסיס – פשוט נתחיל מאיברי הקבוצה, ונוסיף להם איברים כל עוד אפשר.

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

הניסוח של הלמה של צורן הוא מעט טכני אך אינו מסובך בצורה יוצאת דופן. נניח שיש לנו קבוצה שמוגדר עליה יחס סדר (כלומר, אפשר להגיד על איברים "א' גדול מב'", ופירוש הדבר יהיה שלא ייתכן ש-ב' גדול מא', ושאם ב' גדול מג' אז גם א' גדול מג'). אז אם לכל "שרשרת" של איברים שמסודרים לפי גודל – \(A_1<A_2<\dots\) (שימו לב – השרשרת לא בהכרח סופית) יש איזה שהוא איבר \(A\) בקבוצה שלנו שהוא גדול מכל איברי השרשרת ("חסם מלעיל" של השרשרת), אז יש איבר מקסימלי בקבוצה שלנו – כזה שאף איבר אחר אינו גדול ממנו.

הבלבול העיקרי בשימוש בלמה במקרה שלנו עשוי לנבוע מכך שהאיברים שעליהם מוגדר יחס הסדר יהיו בעצמן קבוצות, ויחס הסדר יוגדר באמצעות הכלה: הקבוצה \(A_1\) קטנה מהקבוצה \(A_2\) אם ורק אם היא מוכלת בה: \(A_1 \subseteq A_2\).

עכשיו, נניח שנתונה לנו קבוצה בלתי תלויה \(A\) של וקטורים. נגדיר את אוסף הקבוצות שעליו נרצה להפעיל את הלמה של צורן בתור אוסף הקבוצות הבלתי תלויות של איברים שמכילות את \(A\). אם נמצא איזו שהיא קבוצה בלתי תלויה "מקסימלית" \(B\) מבין כל הקבוצות הללו, נסיים. למה? כי מהמקסימליות נובע שכל איבר שנוסיף לה יהפוך אותה לתלויה לינארית (כי אם כשמוסיפים את האיבר \(x\) לקבוצה \(B\) מקבלים שוב קבוצה בלתי תלויה זו סתירה למקסימליות של \(B\), שכן \(B\subseteq B\cup\{x\}\).

כדי להשתמש בלמה של צורן, אם כן, יש צורך לקחת "שרשרת", להראות שיש לה חסם מלעיל. נניח ש-\(A_\Lambda\) היא שרשרת שכזו (האינדקס המשונה – האות היוונית למבדא – בא לציין שהשרשרת אינה בהכרח מכילה מספר בן מניה בלבד של איברים. מי שזה לא מסתדר לו עם קיום יחס הסדר יכול להיזכר שגם על המספרים הממשיים מוגדר יחס סדר). התעלול המקובל הוא להגדיר את חסם המלעיל בתור איחוד כל הקבוצות הללו: \(C=\cup A_\Lambda\). ברור שהוא חסם מלעיל לשרשרת (כי הוא מכיל כל איבר באיחוד), וכל מה שצריך להראות הוא שגם הוא איבר באוסף כל הקבוצות הבלתי תלויות שמכילות את \(A\).

טוב, ברור שהוא מכיל את \(A\) (למה?) אבל פחות ברור שהוא בלתי תלוי. כדי להראות את זה מניחים בשלילה שהוא תלוי ולכן יש מספר סופי של וקטורים \(a_1,\dots,a_n\in C\) שיוצרים את 0 בצירוף לינארי לא טריוויאלי. כאן נכנס העוקץ לתמונה: אמרנו ש-\(C\) היא איחוד של כל ה-\(A_\Lambda\), ולכןכל איבר \(a_i\) שייך לאיזו שהיא קבוצה \(A_i\) מהשרשרת. מכיוון שכולן מקיימות יחס סדר, פשוט בוחרים את הקבוצה הגדולה ביותר מתוך \(n\) הקבוצות הללו ומובטח שהיא תכיל את כל \(n\) האיברים \(a_1,\dots, a_n\) (למה?) אבל הקבוצה הזו היא קבוצה בלתי תלויה, על פי הגדרת השרשרת… ולכן לא ייתכן שהצירוף של \(a_1,\dots, a_n\) נותן 0 בצורה לא טריוויאלית, וזה מסיים את ההוכחה.

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

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

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

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

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

המטרה: שלכל היותר מספר סופי של אנשים יטעו בתשובה שיתנו.

בהצלחה!

לבחור או לא לבחור – זו השאלה

פורסם בתאריך על ידי

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

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

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

ובכן, מה היא אקסיומת הבחירה? היא הטענה הפשוטה הבאה: נניח שיש לנו קבוצה \(X\) של קבוצות לא ריקות. אקסיומת הבחירה אומרת כי קיימת פונקציה המתאימה לכל קבוצה מתוך \(X\) איבר השייך לה. בכתיבה פורמלית: יש פונקציה \(f\) כך שלכל \(A\in X\) מתקיים \(f(A)\in A\).

הנה דוגמה לפונקציה שכזו עבור מקרה ספציפי: נניח ש-\(X=\{\{1,2\},\{a,b,c\}\}\), אז פונקצית בחירה לדוגמה היא הפונקציה הבאה: \(f(\{1,2\})=1, f(\{a,b,c\})=c\).

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

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

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

אם כן, אין תקווה לכתוב פונקצית בחירה לכל קבוצה \(X\), אבל עדיין אנחנו רוצים להניח שקיימת כזו. אז נכון, קיומה של פונקציה שכזו נשמע מעט יותר שנוי במחלוקת – ובכל זאת, מה הבעיה האמיתית? יש לנו אוסף של קבוצות; כל קבוצה בו היא לא ריקה, אז יש בה איבר; אז פשוט "נגיד" שלכל קבוצה באוסף אנחנו מתאימים את האיבר. מה הבעיה?

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

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

בצורה מתמטית התיאור של כל הבלאגן הזה פשוט יותר. נגדיר \(X=\left\{y|y\notin y\right\}\) . אם נניח שזו קבוצה, נגיע מיד לסתירה מכיוון שלא ייתכן ש-\(X\in X\), וגם לא ייתכן שזה לא מתקיים (למה?)

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

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

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

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