בתשובה לירדן ניר, 25/03/03 20:14
 |
|
 |
||
|
||||
 |
קשה לי להאמין שהצלחתי להיסחף עד כדי כך לויכוח על הגדרות... אבל אני לא מצליח להתאפק אז בכל זאת: בעיני המדעיות1 היא תכונה של ה*שאלה* ששואלים. לכן, קריטריון למדעיות צריך לתת לי דרך להחליט האם שאלה מסוימת היא מדעית או לא. וזה, ללא קשר לצורה שבה אני "מתקיף" את השאלה ומנסה לפתור אותה, שיכולה להיות ע"י ניסויים, ע"י הוכחה מתמטית ועוד דברים שונים ומשונים. ---- עכשיו אולי אפרט יותר לגבי השאלה של P מול NP, שלעניות דעתי היא שאלה מתמטית *וגם* מדעית, ואולי אחת השאלות הפתוחות המעניינות ביותר שיש גם במדע וגם במתמטיקה: השאלה הזו עוסקת בבעיות חישוביות. דוגמא לבעיה חישובית: נניח שאתה מנהל בבית-סוהר ויש לך 100 אסירים ואתה צריך לחלק אותם ל3 מחלקות. ונניח שרשומה לך ההיסטוריה של כל זוגות האסירים שהיה בינהם בעבר סכסוך ואסור לשים אותם באותה מחלקה. הבעיה החישובית שעומדת בפניך היא זו: בהנחה שקיימת חלוקה של האסירים ל3 מחלקות כך שלא יהיה באף מחלקה זוג מסוכסך, איך אפשר למצוא חלוקה כזו? יש לבעיה הזו פתרון טריוויאלי שהוא לעבור על כל החלוקות האפשריות של 100 אסירים ל 3 מחלקות עד שנמצא את החלוקה המתאימה. הבעיה היא שמספר החלוקות האפשריות הוא כל כך עצום, עד שגם למחשב-על ייקח משהו כמו 1000 שנים לעבור על כולן. לכן, הפתרון הטריוויאלי הזה ממש לא מעניין. ניסוח שקול לשאלה "האם P=NP?" הוא "האם אפשר לפתור את 'בעית מנהל בית-הסוהר' ביעילות סבירה?".2 הערות לגבי השאלה הזו: 1) התברר שזוהי שאלה מתמטית שאפשר לנסח אותה במדויק בתור שאלה על אוביקטים מתמטיים לחלוטין. 2) התברר שלפתרון לשאלה הזו יש השלכות פרקטיות עצומות, מעבר להקלה על חייהם של מנהלי בתי-סוהר: א) אם אכן יש לבעיה החישובית הנ"ל פתרון יעיל, אז אפשר יהיה לפתור ביעילות מגוון עצום של בעיות חישוביות אחרות: בפרט תהיה לנו אינטילגנציה מלאכותית ברמות שמתוארות במדע הבדיוני. מחשבים יוכלו להחליף מתמטיקאים ולהוכיח משפטים במקומם. בכלל, כנראה שמחשבים יוכלו להחליף בני-אדם ולהיות טובים יותר מהם בכל תחום שהוא כולל מדע, אמנות, ניהול וכו'. ב) לאור המשמעויות המדהימות של זה, לא פלא שרוב החוקרים מאמינים שאין לבעיה החישובית הזו פתרון יעיל. עדיין, אם יצליחו להוכיח שאין פתרון יעיל3, אז גם במקרה זה ייפתחו בפנינו אפשרויות פרקטיות חדשות. בפרט אפשר יהיה לבנות שיטת הצפנה שאף אחד לא יכול לשבור, ועוד כל מיני דברים מופלאים בתחום של הצפנה כגון בחירות אלקטרוניות ששומרות על סודיות באופן מוכח ועוד. בנוסף יהיה אפשר לערוך ניסויים מדעיים שדורשים הגרלות אקראיות מבלי להשתמש כלל במקור אקראיות, או להשתמש במעט מאוד אקראיות. ----- 1 ברור לי ש"מדעי" פה הוא לא ציון לשבח. 2 ההגדרה הפורמלית של "יעילות סבירה" היא לפתור את הבעיה עבור n אסירים בזמן שהוא n בחזקת איזשהו קבוע שלא תלוי ב n. 3 או חיזוקים מסוימים של המשפט הזה |
 |
 |
 |
|
|
|
||
|
||||
|
ההשלכות הפרקטיות שאתה מתאר נשמעות לי לא קשורות לשאלה. תוכל להסביר אולי איך P=NP נותן אינטיליגנציה מלאכותית? אני, למשל, אשמח לראות אלגוריתם AI שעובד אפילו בזמן EXP, יש לך כזה? איך "P שונה מ- NP" נותן אלגוריתם הצפנה או דה-רנדומיזציה? כמובן אלא אם לדעתך "קיום פונקציה אקספוננציאלית שקשה למעגל אקספוננציאלי" הוא "חיזוק מסוים" של "P שונה מ- NP" (וכרגע לא נראה שזה המצב אלא שמדובר בטענות לא תלויות). למעשה מפתיע עד כמה מועטה החשיבות של P=NP בפתרון בעיות "אמיתיות" יחסית למשקל שהשאלה הזו מקבלת במדעי המחשב. אני חושב שאנשים פשוט מעוצבנים מזה שמשנות השישים עובדים על אותה שטות שמסרבת להפתר. |
|
|
|
|
|
|
||
|
||||
|
הרבה בעיות מדעיות אפשר לנסח בצורה הבאה: נתונה לך סדרה של נתונים, מצא את הכלל הכי פשוט1 שמסביר את הסדרה. דוגמאות לבעיות מהצורה הנ"ל: נתונה לך סדרה של תצפיות על תנועות כוכבים, מצא את הכלל הכי פשוט שמסביר אותן. נתונה לך סדרה של מאמרים שהתקבלו ל mathematical review, מצא את המערכת הכי פשוטה שמייצרת את הסדרה הנ"ל, והשתמש במערכת זו ע"מ לנבא את המאמר הבא בסדרה. נתונה לך סדרה של סרטים שזכו באוסקר, מצא את הנוסחא שעומדת מאחורי כל הסרטים הנ"ל, והשתמש בנוסחא ע"מ לייצר סרט חדש שיזכה באוסקר. כנ"ל אפשר לחשוב על סדרת הציורים של רמברנדט, או סדרת המאמרים של פיינמן וכו' אם P=NP אז אפשר יהיה לפתור ביעילות כל בעיה מהסגנון הזה, וזאת הסיבה שאני אומר שמחשבים יוכלו כנראה להחליף אנשים כמעט בכל תחום. ----- 1 ההגדרה של פשוט יכולה להשתנות לפי ההקשר. למשל: הכלל שיש לו את התיאור הכי קצר, מערכת מתמטית שמשתמשת במינימום של אקסיומות, רשת נוירונים הקטנה ביותר האפשרית וכו' |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
(זה נראה איום ונורא) | |
|
|
|
|
|
||
|
||||
|
לגבי ההשלכות של P שונה מ NP : אם P שונה מ NP אז יש בעיה קשה ב NP ב worst-case. חיזוק טבעי הוא שיש one-way-function שהיא בעיה ב NP שהיא קשה ב average case , וגם שיש דרך לייצר עבוד הבעיה הזו מקרים קשים ביחד עם הפתרון להם. במקרה כזה תהיה לנו גם הצפנה וגם דה-רנדומיזציה. חיזוק טבעי אחר הוא שיש בעיה ב NP (ןלכן בפרט ב EXP) שקשה ב worst-case למעגלים לא יוניפורמיים (ולא רק למכונות יוניפורמיות). זה נותן דה-רנדומיזציה. בנוסף יש עבודות שמשיגות דה-רנדומיזציה חלקית תחת הנחות קושי יוניפורמיות (על מכונות הסתברותיות יוניפורמיות). ברור שהאיכות של ההצפנה והדה-רנדומיזציה תלויים ברמת הקושי המדוייקת של NP, כאשר את מקסימום האפליקציות נקבל כאשר הקושי הוא אקספוננציאלי. עם זאת, חשוב לזכור שאם הקושי יתברר להיות סופר-פולינומי אבל קטן, אז בהחלט ייתכן ועדיין אפשר יהיה לקבל חלק מהאפליקציות שקיימות כאשר P=NP (למרות שפחות ביעילות). מלבד זאת, אם "יש אלוהים"1 אז הוא דאג שהקושי של NP יהיה או פולינומי או אקספוננציאלי ולא איזה פונקציה מכוערת באמצע... ----- 1 אני מאמין ב"אלוהי המתמטיקאים" שדואג שהמתמטיקה לא תצא אף פעם מכוערת. |
|
|
|
|
|
|
||
|
||||
|
בקיצור, אם יהיו לנו הרבה תוצאות במדעי-המחשב שעכשיו אין לנו, נוכל לעשות הרבה דברים. יש לי שתי הערות בקשר למסקנה הזו: 1. היא לא ממש קשורה לשאלה P=NP. כרגע המצב ההדדי של 3 השאלות P=NP, קיימת One-way function, קיים Pseudo-random generator יכול להיות כלשהו מבלי לסתור אף תוצאה ידועה. במובן זה (כלומר בהתאם לידע שיש בידינו כעת) ייתכן ושלוש השאלות בלתי תלויות והכרעת P=NP לא תעזור כלל בשתי השאלות האחרות. 2. עליך לזכור כי הכרעת P=NP לא חייבת להיות קונסטרוקטיבית. כלומר ייתכן שנדע להוכיח כי P=NP אבל לא נקבל אלגוריתם יעיל לבעיה NP קשה כתוצאה ישירה מההוכחה. |
|
|
|
|
|
|
||
|
||||
|
תראה, אם תצא בת-קול מהשמיים ותגלה לנו ש P שונה מ NP אז זה באמת לא יעזור לנו מיידית ליותר מדי דברים (למרות שיש דברים שנוכל להסיק מזה, כגון קושי של קירוב). אבל, בהחלט יש תקווה שכשנראה את ההוכחה ש P שונה מ NP, היא תיתן לנו קצת יותר מאשר עצם המשפט. לגבי מה שאמרת: 1. השאלות לא ממש בלתי-תלויות. מה שידוע הוא: א. אם יש one-way-function אז P שונה מ NP וכן קיים pseudorandom generator ב. אם יש בעיה ב NP שקשה למעגלים לא יוניפורמיים אז קיים pseudorandom generator (מסוג שונה מא' אבל עדיין מתאים לדה-רנדומיזציה). באופן קצת יותר מוגבל זה נכון גם אם יש בעיה ב NP שקשה למכונות יוניפורמיות הסתברותיות. ג. אם NP=P אז גם קיים pseudorandom generator (שים לב שבמקרה זה BPP=P). 2. אם אנחנו יודעים ש P=NP, אפילו בדרך לא קונסטרקטיווית (למשל ע"י בת-קול מהשמיים..), אז אפשר לתת אלגוריתם מפורש שמוצא witness בזמן פולינומי ע"י ליכסון על כל האלגוריתמים האפשריים.1 אני מניח שאם אכן תהיה תוצאה כזו, אז ישקיעו הרבה מאוד בלנסות ולבנות מכונה שתריץ את האלגוריתם הזה בצורה היעילה ביותר. אל תשכח שכבר היום אנשים משקיעים הרבה מאמץ בלבנות מכונות שמריצות אלגוריתמים סאב-אקספוננציאלים, רק בשביל לפתור את הבעיה של פירוק מספר לגורמים. דרך אגב, אני מניח שיהיה מאמץ דומה אם נגלה ש NP מוכל ב P/poly. ----------- 1 צריך יהיה לתת מנגנון timeout לאלגוריתם הזה ע"מ שלא ירוץ בזמן אינסופי. אפשר לעצור אותו אחרי כל מספר סופר פולינומי של צעדים. |
|
|
|
|
|
|
||
|
||||
|
זה כבר נהיה קצת מדי טכני בשביל המדיום הזה. אני מתחיל להרגיש כמו עתודאי (סליחה כליל, גולגר). בכל אופן תודה על התשובה. | |
|
|
|
|
|
||
|
||||
|
יכול להיות שהמדעיות היא תכונה של השאלה. מהי בדיוק השאלה שאותה אפשר לפתור גם מדעית וגם מתמטית, על פי טענתך (אם זו טענתך)? האם השאלה היא "מהי חלוקה אפשרית של האסירים בכלא שלי?" על פניה, זו נשמעת לי שאלה מתמטית טהורה (לאו דווקא מעניינת, בהיותה מקרה פרטי): האם אתה יכול להציע דרך חקירה מדעית (=תלויה אמפירית)? אני לא משוכנע שאי אפשר למצוא בעיות או דרכי חקירה שיהיה קשה להכריע אם הן מתמטיות או פיזיקליות. האם מזה נובע שאין הבחנה,או שהקריטריון לא ברור? לא נראה לי: מכך שיש אפור לא נובע שאין הבחנה בין שחור ללבן. |
|
|
|
|
|
|
||
|
||||
|
עוד משהו: מה זה "תלויה אמפירית"? יש לך רשימה של האסירים שהיו ביניהם סכסוכים. הרשימה הזו היא נתון אמפירי. אבל בתנאי הבעיה שלך, הרשימה הזו *נתונה*. את הבעיה אתה יכול לפתור (אם אתה יכול בכלל) ספון במשרדך, בלי ללכת לבדוק שוב את האסירים (או את העולם החיצון בכלל). לכן החקירה הזו אינה אמפירית. | |
|
|
|
|
|
||
|
||||
|
השאלה היא לא לפתור את בעית מנהל-בית הסוהר אלא השאלה היא "האם קיימת שיטה (= אלגוריתם) יעילה לפתור את 'בעית מנהל בית-הסוהר'?" כאשר שוב, מה שמעניין בשאלה הזו היא ההשלכות שלה על פתרון של המון בעיות אחרות, כפי שהזכרתי למעלה. דרך חקירה מדעית אחת להתקיף את השאלה היא לנסות לחשוב על כל מיני אלגוריתמים לפתור את בעית מנהל בית-הסוהר, למצוא כל מיני נתונים מהחיים ולהריץ את האלגוריתמים הנ"ל על הנתונים ולראות אם הם עובדים. כמובן שגם אם נמצא אלגוריתמים שעובד על כל רשימה שנתנו לו, אז לא תהיה לנו וודאות של 100% שהוא אכן עובד גם על רשימות שלא נתנו לו, אבל זה לא נורא, מאחר ובשיטות לא מתמטיות ממילא לעולם לא נגיע לוודאות של 100%. |
|
|
|
|
|
|
||
|
||||
|
אני לא חושב שחקירה בשיטת ניסוי וטעיה היא בהכרח אמפירית. למשל, בדיקת השערת גולדבאך על מיליארד הטבעיים הראשונים היא חקירה מתמטית, ולא אמפירית. כלומר, אין לי התנגדות שיקראו לזה אמפירית, אבל יש הבדל מהותי ומעניין בינה לבין חקירות שממש בודקות את העולם הפיזיקלי. שיטת החקירה שאתה מציע לשאלת קיום האלגוריתם, בהנתן נתונים, נראית לי מתמטית במובן זה, ולא אמפירית. היא תהיה אמפירית אם, כדי לבדוק את נכונות האלגוריתם, ננסה את החלוקה שהאלגו' מציע, עם אסירים ממש, ונבדוק אם הם דוקרים זה את זה. נניח שיתברר שבמאה ניסויים כאלה האסירים כן או לא דקרו זה את זה. האם תסיק מכך שהאלגו' נכון (או שגוי)? נראה לי שלא. אתה לא באמת תחקור באופן הזה. אם אני מבין נכון, שיטת החקירה שלך היא שנכונות השיבוץ נבדקת גם היא על-פי נתונים *ידועים מראש*. כאמור, אפשר לעשות אותה מהכורסה במשרד, בלי להטריח את העולם הפיזיקלי הרלוונטי (אסירים בשר ודם); לא אמפיריקה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |