P נגד NP ומדליות פילדס. שתי הערות לסדר היום

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

אלו ימים מרתקים למתמטיקה. מלבד מדליית פילדס (ראו סוף הפוסט), הוכרזה החודש הוכחה לבעית המילניום, 'האם P שווה ל – NP'. בעיה ששואלת (בגדול וממש ממש לא בדיוק) האם יש בעיות שאי אפשר לפתור, ריאלית, עם שיטות המחשב שיש לנו כיום? זו אחת הבעיות המפורסמות במתמטיקה, וכנראה הבעיה החשובה ביותר במדעי המחשב. וכמו שנרמז בפיסקה הראשונה, ב – 6 לחודש אוגוסט הכריז וינאי דאולאליקר (Vinay Deolalikar), בחור ממעבדות HP שמוגדר כ'חוקר רציני', שהוא פתר את הבעיה.

[מתמטיקה הורגת עצים?! אנשים הורגים עצים!]

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

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

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

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

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