בתשובה לבועז, 25/03/03 21:20
 |
|
 |
||
|
||||
 |
ההשלכות הפרקטיות שאתה מתאר נשמעות לי לא קשורות לשאלה. תוכל להסביר אולי איך 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 לאלגוריתם הזה ע"מ שלא ירוץ בזמן אינסופי. אפשר לעצור אותו אחרי כל מספר סופר פולינומי של צעדים. |
|
|
|
|
|
|
||
|
||||
|
זה כבר נהיה קצת מדי טכני בשביל המדיום הזה. אני מתחיל להרגיש כמו עתודאי (סליחה כליל, גולגר). בכל אופן תודה על התשובה. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |