בתשובה לגדי אלכסנדרוביץ', 15/06/08 9:22
 |
|
 |
||
|
||||
 |
כל העניין בבעיות עם סיבוכיות לא-פולינומית, הוא שאפילו עם מיליארדי מחשבים, אי-אפשר לפתור מופעים גדולים מספיק שלהם. זה שמצליחים לפרק מספרים, אתה בוודאי יודע, זה ממש לא מרשים - אני יכול לפרק חלק בראש; גדולים יותר אפשר עם עשרות אלפי מחשבים; גדולים מספיק, במידה ובעיית הפירוק אכן לא פולינומית, אי-אפשר יהיה גם אם כל אטום בודד ביקום יהיה מעבד מרובה ליבות. אני בוודאי לא צריך להזכיר לך זאת, אבל לא יזיק שיופיע בפרוטוקול - גם עם בעיות ליניאריות, יש מופעים שאי-אפשר לפתור לפני מות היקום עם מיליארדי מחשבים. החלק המעניין, לצרכי קריפטוגרפיה, הוא שהשחקנים הישרים עדיין יכולים לפעול בזמן סביר, בעוד שלתוקף אין שום דרך מלבד זו הדורשת את המשאבים שאין, ולעולם לא יהיו, בנמצא. אני רוצה לחזור על הנקודה שלי, שנדמה לי (סלח לי) שהיא נכונה, פשוטה, ושחמקה ממך באופן מפתיע עד עכשיו (או שאתה מנסה לדבר על משהו אחר, ואני זה שמתבלבל) - יהי סט של בעיות שאפשר לפתור כל אחת מהן בנפרד, או את כולן ביחד. אתה אומר - יש יותר אינטרס לאנשים להשקיע בפתרון הכללי שפותר את כולן ביחד. אני אומר - כל עוד לא זה אפשרי ולא זה אפשרי - בכלל - מידת האינטרס לא משנה. בלתי-אפשרי נשאר בלתי-אפשרי גם אם עובדים בצוות. "נסה לשחזר את הדוגמה שלי עם משהו שאי אפשר לייצר בקלות" - עזור לי בבקשה. |
 |
 |
 |
|
|
|
||
|
||||
|
העניין של "גדולים מספיק אי אפשר גם אם כל אטום ביקום יהיה מעבד מרובה ליבות" נכון, כמובן, גם לדברים עם סיבוכיות פולינומית, כך שאני מציע שתזנח לרגע את גישת ה"אם משהו הוא לא פולינומי, אין שום סיכוי לחשב אותו". הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק. אנסה לחדד את הנקודה. אני מבדיל בין שלושה סוגי חישובים - כאלו שהם בלתי פיזיביליים בכלל, ועליהם לא מדברים; כאלו שהם קלים וכל מחשב ביתי עושה בצורה זריזה (לצורך הדיון, אלו הפולינומיים); וכאלו שהם "בינוניים" - במחשב ביתי זה ייקח יותר מדי זמן, אבל אם כל המחשבים בעולם יתאגדו וישתפו פעולה, ויחכו חודש חודשיים, החישוב יסתיים. עכשיו, בוודאי שיש הבדל מהותי בין הסיטואציה שבה בכל פעם שרוצים לפרוץ הודעה צריך לבצע חישוב "בינוני" שכזה, ובין הסיטואציה שבה מספיק שכל העולם יבצע פעם אחת את החישוב ה"בינוני" ואז כל אחד יוכל לפרוץ בקלות הודעות קצרות מספיק. המשמעות של זה פשוטה, והיא זו שניסיתי להסביר בהודעה האחרת שאליה הגבת - אם בעיה כלשהי היא כרגע בטווח ה"בינוני", אז למרות שהאלגוריתם שפותר אותה הוא אקספוננציאלי ואפשר להפוך אותה לבלתי אפשרית על ידי הגדלת פרמטר הבטיחות של ההצפנה, בכל זאת היא תגרום לנו לעשות משהו מעשי מאוד - להגדיל את פרמטר הבטיחות של ההצפנה, אולי בצורה לא טריוויאלית, בטח בקפיצה שלה לא ציפינו. הסיבה שבגללה פרמטר הבטיחות גדל בדרך כלל היא שהפתרון הנאיבי (שגם הוא לא פיזיבילי בהינתן פרמטר גדול מספיק) מתחיל להיות מאיים - ולכן גם אלגוריתמים לא יעילים אחרים מסוגלים להיות מאיימים. |
|
|
|
|
|
|
||
|
||||
|
(אמרתי בעצמי שגם לליניארי זה נכון עבור ערכים מסויימים. הסברתי למה עבור ליניאריים זה לא מעניין, ועבור לא-פולינומיים כן - כי השחקנים הישרים נשארים בזמן סביר.) "הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק." - זו לא נקודה מעניינת, כי, לאור הפסקה הקודמת שלי, אין שום סיבה שלא לבחור בהצפנה דווקא את סט הערכים שאינם נמוכים מספיק. (כלומר, יש יתרונות לכך - הצפנה בשניות במקום בשעות - אבל זה לא מחויב המציאות. במידת הצורך, יהיה אפשר לעשות את ההקרבה הזאת, ולהשיג שוב סודיות טובה, במחיר הנוחות של הצפנה כמעט-מיידית.) -- כלומר, הנקודה שלך לאורך הדיון הייתה שיש תרחישים שבהם התקדמות אלגוריתמית דורשת הגדלה של קבוע הבטיחות הנפוץ בהצפנה? מן הסתם אני מסכים. |
|
|
|
|
|
|
||
|
||||
|
בדיוק. אם בגלל איזו תגלית תיאורטית שמעידה על תוצאה ''בלתי אפשרית'' לכאורה גורמת לצורך להצפין בשעות במקום בשניות - כנראה שבכל זאת מדובר במשהו בעל השלכות מעשיות. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |