 |
|
 |
||
|
||||
 |
האם הבעיות הפתוחות במדעי המחשב (ובראשן "P=NP?") מושכות אף הן מיני מטורללים ו"הוכחות" באמתחותיהם? |  |
 |
 |
|
|
|
||
|
||||
|
קודם כל: P=NP <=> P=0 or N=1 ובלי קשר בדיוק התפרסם פתרון לבעייה מתמטית שניתן לסווג אותה כטרחנית: |
|
|
|
|
|
|
||
|
||||
|
בהחלט. הנה דוגמה שראיתי במקרה בזמן האחרון: הפעם לפנינו טרחן-כפייתי מהסוג המשכיל יחסית. רמז לכפייתיות: שים לב כמה גרסאות של מאמר בן שלושה עמודים הופקדו בארכיב במהלך שלושה חודשים. |
|
|
|
|
|
|
||
|
||||
|
מדוע ארקסייב פרסמו את המאמר אם הוא של טרחן? | |
|
|
|
|
|
||
|
||||
|
הארכיב *כמעט* ואיננו מסנן מאמרים. זה לא עיתון במובן הרגיל, אלא ארכיון ל-preprints. אין משמעות לכך שמשהו התפרסם שם, אלא שזה מאוד נוח, ולמרבה המזל עד היום יחסית מעט טרחנים כפייתיים התלבשו עליו. אבל יש בהחלט עוד דוגמאות. | |
|
|
|
|
|
||
|
||||
|
אלון, התוכל לבדוק את המאמר ששלח משתמש eljose79 בפורום של פיזיקספורומוס ולבדוק אם גם הוא טרחן? הקישור:http://physicsforums.com/showthread.php?s=&threa... הוא טוען שיש לו פיתרון לפונקציה הראשונית. תודה מראש. |
|
|
|
|
|
|
||
|
||||
|
מהתבוננות ראשונה: לא ברור לי איזו בעייה הוא חושב שהוא פתר, וכן לא ברור לי מה הפתרון. שטחית, השימוש בטרנספורמים אינטגרליים על-מנת לקבל ביטוי מפורש לפאי-של-איקס כבר מצינו אצל רימאן. כלומר, עצם האפשרות לרשום פונקציה זו כסוג של טרנספורם (בד"כ של הפונקציה זיטא) הוא לא חדש. מההודעה שהאיש שלח לאותו פורום פיסיקלי עולה כי: 1. הוא חושב שהוא "פתר את הבעייה של פאי-של-איקס!!!" מהי? 2. מתנכלים לו, והוא חושד שיגנבו לו את הרעיון. 3. ממאמרו אפשר "לקבל את כל הראשוניים". מה זאת אומרת? ואיפה זה במאמר? אפשר לקבל את כל הראשוניים גם מהנפה של ארתוסטנס. המאמר עצמו מתחיל ב-"במסמך זה אנו מעמידים פנים שביכולתנו להביא גישה חדשה...": בטח סתם שגיאה באנגלית, אבל חמודה. בהמשך הוא מגדיר כמה פונקציות, מחליף חופשי סכימות ואינטגרלים, ובשורה התחתונה מגיע לביטוי סבוך למדי שלא נראה שימושי כלל, גם בהנחה שאפשר לחלץ ממנו משהו נכון. באיזשהו שלב הוא כותב שייאלץ "להסתפק בקירוב", לא ראיתי איפה הוא קירב אבל קירובים לפונקציה הנדונה ידועים כבר מזמן. הייתי אומר שלפנינו טרחן כפייתי בהתהוות. יש איזושהי סיבה מיוחדת שאתה מתעניין בו? |
|
|
|
|
|
|
||
|
||||
|
אני מתכתב בפורום שם ונתקלתי בו אז חשבתי להוסיף אותו לרשימה של הטרחנים שלך. (-: | |
|
|
|
|
|
||
|
||||
|
מתוך אחת הגרסאות (עוד לפני ש"אלו-ים" התווסף להכרת-התודה בסוף): "מאז שהמחבר פרסם מאמר זה באינטרנט, הוא קיבל הערות רבות מאנשים שלא האמינו לו. [...] גרוע מכך, חודש אחרי שהכותב הפיץ את ההוכחה, אפילו הוא לא האמין לה בקריאה ראשונה". אפילו! |
|
|
|
|
|
|
||
|
||||
|
בכל מבחן בקורס באלגוריתמים יש לפחות 3-4 אנשים שמוכיחים ש- P=NP. | |
|
|
|
|
|
||
|
||||
|
אני יכולה לחשוב על לפחות מקרה אחד שבו זה נכון...(: | |
|
|
|
|
|
||
|
||||
|
גיליתי, נדהמתי, והחלטתי לחלוק: ציינתי במאמר שאין הוכחה שמשפט פרמה הוא "קשה". מסתבר שעבור 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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |