בתשובה לגדי אלכסנדרוביץ', 12/05/06 16:15
P=NP כמובן 384932
מהניסוח שלך משתמע שעצם מציאת הוכחה לכך ש-P=NP, די בה כדי להפוך שיטות הצפנה אופרטיביות ללא רלבנטיות. הטענה הזאת נראית לי לא טריוויאלית ‏1. התואיל להסביר מדוע זה כך?

1 הוכחות מתמטיות שעוסקות במקרים כלליים, אינן מציעות בהכרח שיטות סדורות למציאת פתרונות עבור מקרים פרטיים.
P=NP כמובן 384955
הבקיאות שלי בקריפטוגרפיה אפסית, אבל ככל הידוע לי, רוב שיטות ההצפנה שמשמשות אותנו כיום מתבססות על בעיות שהן ב-NP אבל לא ידוע אם הן ב-P. זה לא מקרי - אם משהו ב-NP זה אומר שהוא קל במובן אחד אבל לא בהכרח קל במובן שני - קל לבדוק לו פתרון, אבל לא בהכרח קל למצוא לו פתרון. באותו המובן אנחנו רוצים שמשהו יהיה קל לפענוח אם יודעים מה המפתח, אבל יהיה קשה למצוא את המפתח אם הוא לא ידוע.

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

אגב, כדאי לזכור שטענה כמו P=NP תהיה מלווה *ככל הנראה* בהוכחה קונסרקטיבית - יודגם איך ניתן לפתור בעיה כלשהי שהיא NP שלמה בזמן פולינומיאלי. מכאן אפשר לגזור דרך אופרטיבית לפתור כל בעיה ב-NP בעזרת רדוקציה לבעיה שכבר פתרנו (וגם רדוקציות כאלו כבר ידוע איך לבנות בצורה מעשית). לכן מספיק לומר "שיטת ההצפנה הזו מתבססת על בעיה ב-NP" כדי שיהיה בטוח שאם נוכיח ש-P=NP בצורה קונסטרקטיבית, זה הסוף.
P=NP כמובן 385015
חוץ מהוכחה לא-קונסטרוקטיבית, עוד אפשרות שתציל את ההצפנות היא שהאלגוריתם שיימצא יהיה פולינומיאלי, אבל עם קבועים (חזקה אלף) שיהפכו אותו ללא מעשי עבור השימושים המעשיים בהצפנות.
מה שירדן אמר, בערך. 385090
כולנו יודעים שלזהות הוכחה הרבה יותר קל מלחבר הוכחה.
אם חלילה יתגלה ש-P=NP, העובדה הזו לא תשתנה. מה שישתנה תהיה המשמעות שאנו מעניקים להגדרה המתמטית של P: לא יהיה ניתן יותר לומר שהיא מכילה רק שפות קלות-להכרעה, ונצטרך לאפיין את המושג "קל לחישוב" בצורה יותר עדינה.
מה שירדן אמר, בערך. 385155
אני לא מבין למה זה נכון. כבר עכשיו P מכילה גם שפות שאפשר להכריע רק בזמן שהוא פולינום בחזקת גוגול (אני בטוח שאפשר להנדס כזו שפה, לא?), אז כבר עכשיו קשה להגיד שזה "קל להכרעה".
מה שירדן אמר, בערך. 385188
נכון, הגזמתי לגבי המשמעות של P. היא מכילה גם הרבה דברים מאוד קשים להכרעה. אני אצטרך לחשוב על זה, כנראה ששוויון אינו בהכרח אסון..
מה שירדן אמר, בערך. 385217
הוא *עלול* להיות אסון למי שמשתמש בהצפנה (ה"עלול" מגיע מירדן).
מה שירדן אמר, בערך. 385239
אולי אני מפספס משהו ממש בסיסי אבל אני לא משוכנע שזה נכון. אתה יכול לחשוב על הוכחה? נניח שהמודל שלנו הוא מכונת טיורינג (או כל מודל אחר שאתה מעדיף).
מה שירדן אמר, בערך. 385242
אתה לא משוכנע שמה נכון? שקיימות בעיות שהפתרון שלהם הוא חזקה בגודל הזה? זו תוצאה של מה שמכונה Time hierarchy theorem.

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

אולי ההוכחה שיש בויקיפדיה האנגלית כן קונסטרקטיבית:

מה שירדן אמר, בערך. 385250
אתה צודק. זכרתי שיש משפט היררכיה של המקום אבל לא משפט היררכיה (פולינומי) של הזמן. טעות שלי.
מה שירדן אמר, בערך. 385253
עד כמה שאני מבין (למרות שאני קצת פחות סומך על עצמי כרגע) ההוכחה (שאני מכיר) היא כן קונסטרוקטיבית. מוכיחים ששפת כל המכונות M והקלטים x כך ש- M מקבלת את x בפחות מ- f(|x|) צעדים היא כריעה בזמן f^3 (נגיד) ולא כריעה בזמן f(n/2).

לכן לכל n^k קל להראות שפה פולינומית שלא חשיבה ב- n^k.
מה שירדן אמר, בערך. 385247
מה של גוגול? אולי התכוונת לצ'כוב?
מה שירדן אמר, בערך. 385248
"This article is about the large number. For the Internet company, see Google. For the author, see Gogol"

http://en.wikipedia.org/wiki/Googol
מה שירדן אמר, בערך. 387649
את הסופר אני לא מכיר, אבל מסתבר שיש קשר בין מנוע החיפוש לבין המספר בעל מאה האפסים. למעשה, השם Google מקורו כולו בעיוות שם המספר, שנעשה בטעות על ידי מפתחי המנוע.
מה שירדן אמר, בערך. 387652
כן, זה אחד מפרטי הטריוויה הרבים על החברה הזו (ידעת שה-"Page rank" נקרא על שם פייג', אחד ממקימי החברה?). מצאתי את עצמי פעם אומר "גוגל" במקום "גוגול", למרבה המבוכה.

אתה לא מכיר את גוגול או שלא קראת את גוגול?
מה שירדן אמר, בערך. 387679
לא מכיר, למרבה הבושה.
מה שירדן אמר, בערך. 387691
בשביל זה יש ויקיפדיה (ותרגומים לעברית של ספרים שלו).

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

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