בתשובה למיץ פטל, 18/08/03 11:43
 |
|
 |
||
|
||||
 |
גיליתי, נדהמתי, והחלטתי לחלוק: ציינתי במאמר שאין הוכחה שמשפט פרמה הוא "קשה". מסתבר שעבור P=NP זה לא נכון: *יש* הוכחה פורמלית שכדי להוכיח ש-P שונה מ-NP *צריך להמציא שיטה חדשה ממש*. כל השיטות הידועות להוכחת חסמים תחתונים, ולמעשה כל שיטה שנשמעת סבירה, לא תצלח - ליתר דיוק, אם תצלח, אז משהו מאוד בלתי-סביר יקרה. אם יש עניין, אנסה להסביר יותר. הנה סימוכין למאמר (אני חושש שלא מצאתי אותו ברשת): Razborov, A. and Rudich, S. - Natural Proofs. J. Comput. System Sci. 55 (1997) no. 1 part 1 24--35 הופיע גם ב-STOC 94.לעניין הטרחנים: אין שום סיכוי, כמובן, שעובדה זו תפריע להם. |
 |
 |
 |
|
|
|
||
|
||||
|
במגוון פורמטים: http://citeseer.nj.nec.com/86771.html | |
|
|
|
|
|
||
|
||||
|
לשני המחברים יש דף בית. רזבורוב: רודיך: המאמר הנ"ל מראה שלא תיתכן הוכחה "טבעית" שP שונה מNP, אלא אם כן לכל פונקציה יעילה, אפשר לחשב באופן יעיל את הפונקציה ההופכית שלה. בפרט לא תיתכן הוכחה כזו אם בעית ה factoring היא קשה. שים לב, שלאור העובדה שכל השיטות הידועות היום להוכחת חסמים תחתונים לא מדגדגות את בעית P מול NP, גם בלי המאמר הזה ברור שצריך יהיה למצוא שיטה חדשה ממש כדי לפתור אותה. |
|
|
|
|
|
|
||
|
||||
|
מסכים, אבל "לא מדגדגות" ו-"ברור" זה אחרת מהגדרה פורמלית ומשכנעת של הוכחה "טבעית", והוכחה פורמלית שאין כזו אלא אם השמיים נופלים ( = קל לפרק לגורמים). כל השיטות שבידינו לא מדגדגות את בעיית ה-3n+1, או את השאלה אם פאי מספר נורמלי. כולם חשים שצריך שיטות חדשות, אבל אם מישהו *יוכיח* את זה, זה יהיה מרשים מאוד. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |