בתשובה לunspammable, 23/12/06 21:40
 |
|
 |
||
|
||||
 |
הדרקון שלי במרתף שותה בדיוק מקנקן תה שכזה. ארל גריי, שתי קוביות סוכר (ובבקשה נא להוציא את הפטיש)1. אני לא חושב שיש אי הסכמות מהותיות בינינו, מלבד דבר אחד: התפלשות במתמטיקה ולוגיקה זה לא "סתם" ולא "לא פרקטי". טענות מתמטיות לא אומרות יותר או פחות מהתוכן שלהן (זה בעיקר מ שיפה בהן), אבל לא הייתי מגזים ואומר שאין להן השלכות פרקטיות או קשר למציאות. אני חושב שהנקודה הזאת תהיה הרבה יותר ברורה לקהל במאמר הבא של גדי שידבר (כך הבנתי) גם על בעיות קשות ולא רק על בעיות בלתי אפשריות (כמובן שגם אז יקפצו כמה טכנואידים ויגידו - למי אכפת אם P=NP או לא? זה קשקוש מתמטי שלא קשור לחיים האמיתיים. אתמול כתבתי ב-#C אלגוריתם היוריסטי שיכול...). _________ 1 באנגלית ועם באגס באני, זה יותר מצחיק. |
 |
 |
 |
|
|
|
||
|
||||
|
>> אני לא חושב שיש אי הסכמות מהותיות בינינו, מלבד דבר אחד: התפלשות במתמטיקה ולוגיקה זה לא "סתם" ולא "לא פרקטי". את זה לא טענתי. |
|
|
|
|
|
|
||
|
||||
|
מה שנחמד ב-P=NP זה שיש לו דוגמה (לעוסה ביותר, כמובן) שמחסלת את הטכנואיד שלך - הצפנת מפתח ציבורי. כשהטכנואיד יכתוב ב-#C אלגוריתם היוריסטי שמפצח את RSA בשתי שניות, אז אפשר יהיה לומר שהוכחה ש-P שונה מ-NP זה שטויות. (מה שנחמד כאן הוא שה"לא מעניין אף אחד" הולך, אם בכלל, לכיוון השני - דווקא הוכחות שמשהו *כן* ב-P לא בהכרח מעניינות מישהו - אז מה אם הוכיחו שבדיקת ראשוניות היא ב-P? מישהו יפסיק להשתמש באלגוריתם של רבין ויעבור לאלגוריתם הדטרמיניסטי בגלל זה?) |
|
|
|
|
|
|
||
|
||||
|
זה ספציפית דווקא לא יעבוד - כיוון שפירוק מספרים איננו NP-Complete (או לפחות לא הוכח שזה המצב), יתכן בהחלט שניתן "לפצח את RSA בשתי שניות" (למצוא אלגוריתם פולינומיאלי לפירוק מספרים), אבל עדיין ישארו בעיות שהן "באמת" לא ב-P ולא נוכל לפתור אותן לעולם. למעשה, אני מאמין שזה בדיוק המצב (כלומר פירוק מספרים הוא ב-P, אבל P שונה מ-NP) |
|
|
|
|
|
|
||
|
||||
|
נכון שזה לא יעבוד בצורה מוחלטת אבל הוכחה כזו בהחלט "תרגיע חלקית" את מי שחושש שימצאו דרך טובה לעשות את זה (במרכאות, כי אני מניח שרוב האנשים שמתעסקים בזה ממילא מניחים ש-P שונה מ-NP). אגב, גם אם פירוק מספרים אינו NP-שלם, זה עדיין לא אומר שהוא שייך ל-P אפילו אם P שונה מ-NP (תחושת הבטן הלא מבוססת שלי היא שהוא לא NP שלם אבל גם לא ב-P) - אבל אולי באמת כדאי לשמור את זה למאמר הבא. |
|
|
|
|
|
|
||
|
||||
|
לא נראה לי חוקי במיוחד להחזיק דרקון במרתף כל כך הרבה זמן. יש לך רישיון מיוחד לזה? | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |