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

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

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

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

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

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

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

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

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

10 תגובות

  1. חנן כהן הגיב:

    התקטננות – מדליית פילדס. על שם המתמטיקאי John Charles Fields

  2. ניימן הגיב:

    אתה צודק לגמרי ואני יודע את זה. לא יודע מה עבר לי בראש :]

  3. חנן כהן הגיב:

    אני (חושב שאני) יודע מה עבר לך בראש: פילדס' = של פילד ולכן "מדליית פילד"

  4. ר. הגיב:

    התקטננות 2 — אילון, לא אלון.

  5. כשכתבת במייל שכולם מפחדים ממתמטיקה, העלית בי גל זכרונות מספר ילדות נשכח-
    אני שונא מתמטיקה.
    http://simania.co.il/bookdetails.php?item_id=8763
    כמובן שאין לזה דבר וחצי דבר עם המתמטיקה שלך, אבל אי אפשר לבוא בתלונות לאסוציאציות.
    בכל אופן זה ספר שמאוד אהבתי בילדות, וקראתי בו שוב ושוב.

  6. ניימן הגיב:

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

    לא סוגרת ת'פה: לא מכיר ת'ספר. אפשר תקציר על מה הוא?

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

  8. ניימן הגיב:

    תמיד ידעתי שאת אחת משלנו!

  9. ניימן, זה ספר לילדים. בבית ספר יסודי. אני לא בטוחה שזה הופך אותי לאחת משלכם.

  1. 29 בספטמבר 2010

    […] נתחיל, למען הסדר הטוב, בנקודה בה נגענו פעם שעברה. פתרון בעית המילניום P שווה ל – NP (ע"י מתן תשובה […]

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *

Subscribe without commenting