בתשובה למ. השור, 26/03/03 0:19
-- אזהרה: תגובה טיפה טכנית -- 137607
בועז • בתשובה למ. השור יום ד', 26/3/2003, 16:32
לגבי ההשלכות של P שונה מ NP :

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

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

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

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

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

-----

‏1 אני מאמין ב"אלוהי המתמטיקאים" שדואג שהמתמטיקה לא תצא אף פעם מכוערת.
-- אזהרה: תגובה טיפה טכנית -- 137647
מ. השור • בתשובה לבועז יום ד', 26/3/2003, 21:05
בקיצור, אם יהיו לנו הרבה תוצאות במדעי-המחשב שעכשיו אין לנו, נוכל לעשות הרבה דברים. יש לי שתי הערות בקשר למסקנה הזו:

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

2. עליך לזכור כי הכרעת P=NP לא חייבת להיות קונסטרוקטיבית. כלומר ייתכן שנדע להוכיח כי P=NP אבל לא נקבל אלגוריתם יעיל לבעיה NP קשה כתוצאה ישירה מההוכחה.
-- אזהרה: תגובה טיפה טכנית -- 137652
בועז • בתשובה למ. השור יום ד', 26/3/2003, 22:24
תראה, אם תצא בת-קול מהשמיים ותגלה לנו ש 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
מ. השור • בתשובה לבועז יום ד', 26/3/2003, 23:28
זה כבר נהיה קצת מדי טכני בשביל המדיום הזה. אני מתחיל להרגיש כמו עתודאי (סליחה כליל, גולגר). בכל אופן תודה על התשובה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות