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