בתשובה לunspammable, 23/12/06 21:40
שתי הערות 425930
הדרקון שלי במרתף שותה בדיוק מקנקן תה שכזה. ארל גריי, שתי קוביות סוכר (ובבקשה נא להוציא את הפטיש)‏1.

אני לא חושב שיש אי הסכמות מהותיות בינינו, מלבד דבר אחד: התפלשות במתמטיקה ולוגיקה זה לא "סתם" ולא "לא פרקטי".

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

_________
1 באנגלית ועם באגס באני, זה יותר מצחיק.
שתי הערות 425938
>> אני לא חושב שיש אי הסכמות מהותיות בינינו, מלבד דבר אחד: התפלשות במתמטיקה ולוגיקה זה לא "סתם" ולא "לא פרקטי".

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

(מה שנחמד כאן הוא שה"לא מעניין אף אחד" הולך, אם בכלל, לכיוון השני - דווקא הוכחות שמשהו *כן* ב-P לא בהכרח מעניינות מישהו - אז מה אם הוכיחו שבדיקת ראשוניות היא ב-P? מישהו יפסיק להשתמש באלגוריתם של רבין ויעבור לאלגוריתם הדטרמיניסטי בגלל זה?)
שתי הערות 425984
זה ספציפית דווקא לא יעבוד - כיוון שפירוק מספרים איננו NP-Complete (או לפחות לא הוכח שזה המצב), יתכן בהחלט שניתן "לפצח את RSA בשתי שניות" (למצוא אלגוריתם פולינומיאלי לפירוק מספרים), אבל עדיין ישארו בעיות שהן "באמת" לא ב-P ולא נוכל לפתור אותן לעולם.

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

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

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים