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