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

‏1 הוכחות מתמטיות שעוסקות במקרים כלליים, אינן מציעות בהכרח שיטות סדורות למציאת פתרונות עבור מקרים פרטיים.
P=NP כמובן 384955
גדי אלכסנדרוביץ' • בתשובה להקשה המקשה שבת, 13/5/2006, 12:52
הבקיאות שלי בקריפטוגרפיה אפסית, אבל ככל הידוע לי, רוב שיטות ההצפנה שמשמשות אותנו כיום מתבססות על בעיות שהן ב-NP אבל לא ידוע אם הן ב-P. זה לא מקרי - אם משהו ב-NP זה אומר שהוא קל במובן אחד אבל לא בהכרח קל במובן שני - קל לבדוק לו פתרון, אבל לא בהכרח קל למצוא לו פתרון. באותו המובן אנחנו רוצים שמשהו יהיה קל לפענוח אם יודעים מה המפתח, אבל יהיה קשה למצוא את המפתח אם הוא לא ידוע.

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

אגב, כדאי לזכור שטענה כמו P=NP תהיה מלווה *ככל הנראה* בהוכחה קונסרקטיבית - יודגם איך ניתן לפתור בעיה כלשהי שהיא NP שלמה בזמן פולינומיאלי. מכאן אפשר לגזור דרך אופרטיבית לפתור כל בעיה ב-NP בעזרת רדוקציה לבעיה שכבר פתרנו (וגם רדוקציות כאלו כבר ידוע איך לבנות בצורה מעשית). לכן מספיק לומר "שיטת ההצפנה הזו מתבססת על בעיה ב-NP" כדי שיהיה בטוח שאם נוכיח ש-P=NP בצורה קונסטרקטיבית, זה הסוף.
P=NP כמובן 385015
ירדן ניר-בוכבינדר • בתשובה לגדי אלכסנדרוביץ' שבת, 13/5/2006, 21:31
חוץ מהוכחה לא-קונסטרוקטיבית, עוד אפשרות שתציל את ההצפנות היא שהאלגוריתם שיימצא יהיה פולינומיאלי, אבל עם קבועים (חזקה אלף) שיהפכו אותו ללא מעשי עבור השימושים המעשיים בהצפנות.
מה שירדן אמר, בערך. 385090
. • בתשובה לירדן ניר-בוכבינדר יום א', 14/5/2006, 8:56
כולנו יודעים שלזהות הוכחה הרבה יותר קל מלחבר הוכחה.
אם חלילה יתגלה ש-P=NP, העובדה הזו לא תשתנה. מה שישתנה תהיה המשמעות שאנו מעניקים להגדרה המתמטית של P: לא יהיה ניתן יותר לומר שהיא מכילה רק שפות קלות-להכרעה, ונצטרך לאפיין את המושג "קל לחישוב" בצורה יותר עדינה.
מה שירדן אמר, בערך. 385155
גדי אלכסנדרוביץ' • בתשובה ל. יום א', 14/5/2006, 14:11
אני לא מבין למה זה נכון. כבר עכשיו P מכילה גם שפות שאפשר להכריע רק בזמן שהוא פולינום בחזקת גוגול (אני בטוח שאפשר להנדס כזו שפה, לא?), אז כבר עכשיו קשה להגיד שזה "קל להכרעה".
מה שירדן אמר, בערך. 385188
. • בתשובה לגדי אלכסנדרוביץ' יום א', 14/5/2006, 15:59
נכון, הגזמתי לגבי המשמעות של P. היא מכילה גם הרבה דברים מאוד קשים להכרעה. אני אצטרך לחשוב על זה, כנראה ששוויון אינו בהכרח אסון..
מה שירדן אמר, בערך. 385217
גדי אלכסנדרוביץ' • בתשובה ל. יום א', 14/5/2006, 16:55
הוא *עלול* להיות אסון למי שמשתמש בהצפנה (ה"עלול" מגיע מירדן).
מה שירדן אמר, בערך. 385239
מ. השור • בתשובה לגדי אלכסנדרוביץ' יום א', 14/5/2006, 18:24
אולי אני מפספס משהו ממש בסיסי אבל אני לא משוכנע שזה נכון. אתה יכול לחשוב על הוכחה? נניח שהמודל שלנו הוא מכונת טיורינג (או כל מודל אחר שאתה מעדיף).
מה שירדן אמר, בערך. 385242
גדי אלכסנדרוביץ' • בתשובה למ. השור יום א', 14/5/2006, 18:44
אתה לא משוכנע שמה נכון? שקיימות בעיות שהפתרון שלהם הוא חזקה בגודל הזה? זו תוצאה של מה שמכונה Time hierarchy theorem.

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

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

לכן לכל n^k קל להראות שפה פולינומית שלא חשיבה ב- n^k.
מה שירדן אמר, בערך. 385247
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' יום א', 14/5/2006, 18:52
מה של גוגול? אולי התכוונת לצ'כוב?
מה שירדן אמר, בערך. 385248
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני יום א', 14/5/2006, 18:55
"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
עמרי גולדשטיין • בתשובה לגדי אלכסנדרוביץ' שבת, 27/5/2006, 14:34
את הסופר אני לא מכיר, אבל מסתבר שיש קשר בין מנוע החיפוש לבין המספר בעל מאה האפסים. למעשה, השם Google מקורו כולו בעיוות שם המספר, שנעשה בטעות על ידי מפתחי המנוע.
מה שירדן אמר, בערך. 387652
גדי אלכסנדרוביץ' • בתשובה לעמרי גולדשטיין שבת, 27/5/2006, 14:42
כן, זה אחד מפרטי הטריוויה הרבים על החברה הזו (ידעת שה-"Page rank" נקרא על שם פייג', אחד ממקימי החברה?). מצאתי את עצמי פעם אומר "גוגל" במקום "גוגול", למרבה המבוכה.

אתה לא מכיר את גוגול או שלא קראת את גוגול?
מה שירדן אמר, בערך. 387679
עמרי גולדשטיין • בתשובה לגדי אלכסנדרוביץ' שבת, 27/5/2006, 18:09
לא מכיר, למרבה הבושה.
מה שירדן אמר, בערך. 387691
גדי אלכסנדרוביץ' • בתשובה לעמרי גולדשטיין שבת, 27/5/2006, 19:27
בשביל זה יש ויקיפדיה (ותרגומים לעברית של ספרים שלו).
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות