בתשובה לבועז, 25/03/03 21:20
לגבי הטענה השניה שלך: 137539
ההשלכות הפרקטיות שאתה מתאר נשמעות לי לא קשורות לשאלה.

תוכל להסביר אולי איך P=NP נותן אינטיליגנציה מלאכותית? אני, למשל, אשמח לראות אלגוריתם AI שעובד אפילו בזמן EXP, יש לך כזה?

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

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

נתונה לך סדרה של נתונים, מצא את הכלל הכי פשוט‏1 שמסביר את הסדרה.

דוגמאות לבעיות מהצורה הנ"ל:

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

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

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

כנ"ל אפשר לחשוב על סדרת הציורים של רמברנדט, או סדרת המאמרים של פיינמן וכו'

אם P=NP אז אפשר יהיה לפתור ביעילות כל בעיה מהסגנון הזה, וזאת הסיבה שאני אומר שמחשבים יוכלו כנראה להחליף אנשים כמעט בכל תחום.

-----

1 ההגדרה של פשוט יכולה להשתנות לפי ההקשר. למשל:
הכלל שיש לו את התיאור הכי קצר, מערכת מתמטית שמשתמשת במינימום של אקסיומות, רשת נוירונים הקטנה ביותר האפשרית וכו'
ראה תגובה 131542 למקורות על השלכות של P מול NP 137608
בבקשה אל תשימו בינתיים קישורים בכותרת 137625
(זה נראה איום ונורא)
-- אזהרה: תגובה טיפה טכנית -- 137607
לגבי ההשלכות של P שונה מ NP :

אם P שונה מ NP אז יש בעיה קשה ב NP ב worst-case. חיזוק טבעי הוא שיש one-way-function שהיא בעיה ב NP שהיא קשה ב average case , וגם שיש דרך לייצר עבוד הבעיה הזו מקרים קשים ביחד עם הפתרון להם. במקרה כזה תהיה לנו גם הצפנה וגם דה-רנדומיזציה.

חיזוק טבעי אחר הוא שיש בעיה ב NP (ןלכן בפרט ב EXP) שקשה ב worst-case למעגלים לא יוניפורמיים (ולא רק למכונות יוניפורמיות). זה נותן דה-רנדומיזציה. בנוסף יש עבודות שמשיגות דה-רנדומיזציה חלקית תחת הנחות קושי יוניפורמיות (על מכונות הסתברותיות יוניפורמיות).

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

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

מלבד זאת, אם "יש אלוהים"‏1 אז הוא דאג שהקושי של NP יהיה או פולינומי או אקספוננציאלי ולא איזה פונקציה מכוערת באמצע...

-----

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

1. היא לא ממש קשורה לשאלה P=NP. כרגע המצב ההדדי של 3 השאלות P=NP, קיימת One-way function, קיים Pseudo-random generator יכול להיות כלשהו מבלי לסתור אף תוצאה ידועה. במובן זה (כלומר בהתאם לידע שיש בידינו כעת) ייתכן ושלוש השאלות בלתי תלויות והכרעת P=NP לא תעזור כלל בשתי השאלות האחרות.

2. עליך לזכור כי הכרעת P=NP לא חייבת להיות קונסטרוקטיבית. כלומר ייתכן שנדע להוכיח כי P=NP אבל לא נקבל אלגוריתם יעיל לבעיה NP קשה כתוצאה ישירה מההוכחה.
-- אזהרה: תגובה טיפה טכנית -- 137652
תראה, אם תצא בת-קול מהשמיים ותגלה לנו ש 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 לאלגוריתם הזה ע"מ שלא ירוץ בזמן אינסופי. אפשר לעצור אותו אחרי כל מספר סופר פולינומי של צעדים.
-- אזהרה: תגובה טיפה טכנית -- 137660
זה כבר נהיה קצת מדי טכני בשביל המדיום הזה. אני מתחיל להרגיש כמו עתודאי (סליחה כליל, גולגר). בכל אופן תודה על התשובה.

חזרה לעמוד הראשי

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים