בתשובה לגדי אלכסנדרוביץ', 10/06/08 6:58
 |
|
 |
||
|
||||
 |
1) נכון. הקשר הוא דווקא פשוט למדי: פתרון חיובי ל-Entsch היה גורר מיד פתרון חיובי לבעייה העשירית, ולהיפך - פתרון שלילי לעשירית היה מראה שה-Entsch לא פתירה. זה כמובן המצב, אלה שההוכחות קרו (כצפוי) בסדר ההפוך. נכון גם שאת שתיהן העלה הילברט, אלא שאת הבעייה העשירית הוא הציע ב-1900, ואת ה-Entscheidungsproblem כמעט 30 שנה מאוחר יותר (ולא כי הוא סתם שכח). המאמר של טיורינג עוסק בזו האחרונה, ואין לו כל קשר למשוואות דיופנטיות ולבעייה העשירית. אם רוצים לנטפק, יש עוד הזדמנויות לרוב במאמר (תיאור המושג "אלגוריתם", למשל), אבל עייפתי מתפקיד הטרחן הלוגי באייל. חייו ויצירתו של טיורינג הם בוודאי מעניינים ומרתקים, ואם כבר מוסיפים קישורים הייתי ממליץ מאוד על הביוגרפיה המצויינת של הודג'ס: ועל הגליון של ה-Notices המוקדש לו ומכיל מאמרים מעניינים לרוב: |
 |
 |
 |
|
|
|
||
|
||||
|
מה הבעיה בתיאור שלהם של "אלגוריתם"? הוא לא Turing-complete? (לא באמת התעמקתי בו) | |
|
|
|
|
|
||
|
||||
|
לא צריך להתעמק. עבור הדיוטות, זה נראה לי כמו תיאור סתום למדי. מה פירוש "האלגוריתם מסוגל לבצע פעולת חיבור, שבאמצעותה ניתן לבצע מניה של מספרים"? למה צריך "לבצע מניה של מספרים", ומה זה בכלל? מה פירוש "מסוגל האלגוריתם לשאול שאלות שהתשובה אליהן היא כן או לא"? הוא מסוגל לשאול אם יש אנשים על הירח? את מי הוא שואל את השאלות? ברור לי שהכוונה היא לתאר את המושג באופן כללי עבור אנשים שאינם בקיאים בתחום. דווקא בהקשר הזה התיאור נראה לי סתום. עוד ניטפוק, לדרך: "רבים מאיתנו סבורים שמחשבים יכולים לבצע כל פעולה חישובית." אני סקרן להבין איך מחקריו של טיורינג מראים את התוצאה המפתיעה שאין זה כך. |
|
|
|
|
|
|
||
|
||||
|
מה נגיד, צודק. אני סקרן לדעת מאיפה הם לקחו את התיאור הזה. | |
|
|
|
|
|
||
|
||||
|
אאז''נ עושים זאת בעזרת מכונת טורינג האוניברסלית (מכונת טיורינג המריצה מכונות טיורינג אחרות וע''י הוכחה בדרך הסתירה (מניחים שכל בעיה ניתנת לפתרון אפקטיבי ויוצרים אלגוריתם שאינו פתיר). אשמח אם מישהו יביא הפנייה להוכחה עצמה, מפני שנראה לי שראיתי אותה באיזשהו ספר שם היא הרבה יותר בהירה מאשר במאמרים של טיורינג. הבעיה היא שההוכחה הזאת נסמכת על התזה של צ'רץ' וטיורינג (בערך ''מכונות טיורינג יכולות לפתור כל בעיה הניתנת לפתרון אפקטיבי''). וזוהי תזה ולא משפט, משום שלמושג פתרון אפקטיבי אין הגדרה פורמלית (''מתמטית''). |
|
|
|
|
|
|
||
|
||||
|
אלון מתלונן על הניסוח. את הרעיון הוא מכיר מ דיון 2762 :-) | |
|
|
|
|
|
||
|
||||
|
יתכן שגם אני ראיתי זאת אצל גדי אבל אני חושב שראיתי עוד ניסוח ממש פשוט (פחות מופשט). לגבי תלונתו שך אלון, אני חושב שזה יותר בבחינת רמז וטענה. המשפט האחרון בתגובתי הקודמת (הלקוח באמת מ"המחשב אינו כל יכול"/דוד הראל) נועד לומר שזו כנראה אינה הוכחה במובן המתמטי. |
|
|
|
|
|
|
||
|
||||
|
לא לזאת כיוונתי (את ההוכחה אני מכיר היטב). הפריע לי הניסוח. ודאי שמחשבים מסוגלים לבצע כל פעולה חישובית, כשם שמלאכים מסוגלים לבצע כל פעולה מלאכית. יש כאן *הנחה* ש"פתרון בעיית העצירה" היא "פעולה חישובית", ומסתבר שהיא איננה כזו. אני מניח שהכוונה היתה, בערך, "לאנשים נדמה שמחשבים יכולים לפתור כל בעייה מוגדרת היטב הנראית כמו בעייה חישובית, אבל הם לא". התיזה של צ'רץ' וטיורינג איננה כפי שציטטת (גם לא בערך). התיזה היא "כל מה שניתן לחישוב במובן אינטואיטיבי כלשהו, ניתן לחישוב ע"י מכונת טיורינג". |
|
|
|
|
|
|
||
|
||||
|
נראה לי שזו הגדרה די צרה של המונח "פעולה חישובית". בפרט, כפי שאתה בטוח מכיר, יש מודלים חישוביים מעניינים מאוד שבהם בעיית העצירה דווקא כריעה. נשמע לי לא מועיל להגביל את המונח "חישוב" למודל אחד ספציפי (וכבר נאמר רבות על הקשר בין "מדעי המחשב" למחשבים). למה לא להגדיר "פעולה חישובית" (למשל) כפונקציה ממחרוזות בינאריות למחרוזות בינאריות? |
|
|
|
|
|
|
||
|
||||
|
אפשר דוגמה למודלים הללו? להגדיר "פעולה חישובית" כפונקציה מטבעיים לטבעיים (הינו הך עם "מחרוזות בינאריות") קצת מעקר את הרעיון של "חישובי" מתוכן. יותר פשוט לקרוא לזה "פונקציה מהטבעיים לטבעיים" וחסל. הרי מה שבאמת מעניין אותנו הוא אם אנחנו מסוגלים להגיע בצורה "מכנית" ("ללא מחשבה" - וכל המרכאות הללו הכרחיות, כמובן) לפלט בהינתן הקלט. |
|
|
|
|
|
|
||
|
||||
|
לפעמים מעניין להסתכל על מצב שבו מותר לתת אלגוריתם אחר לכל גודל של קלט, עם מגבלות מסוימות. חישוב כזה נקרא ''לא יוניפורמי'' ומהמשפט הקודם לא כל כך ברור למה יעניין מישהו להסתכל על סוג כזה של אלגוריתמים, אני אוכל להסביר קצת יותר אם רוצים. בכל אופן, ברור שכל בעיית החלטה (בפרט בעיית העצירה) ניתנת לחישוב במודל הזה בהנחה שהקלט נתון בייצוג אונארי (לכל גודל של קלט או שמגדירים את האלגוריתם שמחזיר תמיד ''כן'' או את האלגוריתם שמחזיר תמיד ''לא''). לפי ההגדרה שלי זה עובד גם כאשר הקלט נתון בייצוג יעיל (לכל גודל התאם את טבלת האמת המתאימה) אבל ה''מגבלות המסוימות'' שציינתי בדרך כלל מונעות הגדרה כזו. ברור שאפשר להגדיר כל דבר איך שרוצים. בעיני ה''פעולות החישוביות'' הן העולם של כל מה שאנחנו יכולים לרצות לחשב. עכשיו אפשר לשאול למשל איזה חלק מהעולם הזה חשיב במכונת טיורינג בזמן סופי, בזמן פולינומי, עם אקראיות, עם אינטראקציה וכל הגדרה רלוונטית אחרת. אני חושב שלא מעניין להגביל את הדיון רק לפונקציות רקורסיביות (כלומר חשיבות בזמן סופי במכונת טיורינג). במילים אחרות, השאלה בעיני היא לא ''האם מסוגלים להגיע מהקלט לפלט במכונת טיורינג'' אלא ''באילו אופנים ובאמצעות אילו משאבים חישוביים אפשר להגיע מהקלט לפלט''. |
|
|
|
|
|
|
||
|
||||
|
אני מכיר מודלים לא יוניפורמיים (בפרט, מעגלים) אבל למרות שהם מעניינים, אני לא בטוח שמישהו חושב עליהם כעל מודל חישובי "אמיתי"; הם מופרכים אפילו יותר מאשר מכונת טיורינג אי דטרמיניסטית נחשבת "אמיתית" בכל הנוגע לזמן ריצה פולינומי. | |
|
|
|
|
|
||
|
||||
|
כנראה יש לפחות מישהו אחד שחושב ככה. למה אתה חושב שמשפחה לא יוניפורמית של מעגלים היא "מופרכת"? דווקא נשמע לי כמו משהו מאוד ממשי. כשחושבים על זה, בתכנון חומרה הרבה פעמים השיקולים הם "לא יוניפורמיים", כלומר מקריבים סקלביליות לטובת יעילות. | |
|
|
|
|
|
||
|
||||
|
אשמח לראות מאמר/ספר של מישהו שחושב ככה. צריך להבדיל בין "חושב שזה מודל חישובי אמיתי" ובין "חושב שזה מעניין" - גם אוטומט Buchi (אוטומט שפועל על מילים אינסופיות, עם קבלה על ידי מעבר אינסוף פעמים במצב מקבל) הוא לא מודל חישובי אמיתי אבל הוא מאוד מעניין ואפילו שימושי. משפחה לא יוניפורמית של מעגלים היא מופרכת כי התיאור שלה הוא לא סופי. כמובן, כשמצמצמים אותה להכיל מספר סופי של "תת משפחות" היא הופכת להיות משהו מעשי מאוד, אבל אז היא גם בוודאי יוניפורמית (לכל סדרה סופית קיימת מכונת טיורינג טריוויאלית שיודעת לחשב אותה). |
|
|
|
|
|
|
||
|
||||
|
שמע, זה קצת קשה כשאתה משחק עם מושגים שאתה המצאת. מה הופך מודל חישובי ל"אמיתי" או להבדיל ל"מופרך"? אני מסכים שאפשר להגדיר את המושגים הללו כך שמכונת טיורינג נכנסת להגדרה ומעגלים לא. אני אעשה עוד ניסיון להסביר למה אני חושב שמשפחת מעגלים לא יוניפורמית היא בעלת קשר ישיר לעולם היישומי (אם זה לא מתאים להגדרה שלך ל"אמיתי", אפשר למצוא מילה אחרת). ננסה דוגמה. בוא נניח (את ההנחה הלא סבירה) שמישהו מוצא אלגוריתם הצפנה שאין לו אלגוריתם הפיכה יעיל אבל יש משפחת מעגלים שהופכת אותו באופן יעיל. לכאורה תרצה לומר שזה לא מעניין. אבל בעצם זה אומר שלכל סטנדרט הצפנה שתפתח באמצעות האלגוריתם הזה. ברגע שגודל המפתח הוחלט, אפשר לעבוד מאוד מאוד קשה ולמצוא את המעגל הרלוונטי ומאותו רגע הסטנדרט הזה לא שווה כלום. |
|
|
|
|
|
|
||
|
||||
|
"אמיתי" לצורך הדיון הוא פשוט "משהו שניתן, בתיאוריה, לממש במציאות". החלק של ה"לעבוד מאוד מאוד קשה ולמצוא את המעגל הרלוונטי" הוא די מעניין - לדעתי אתה נוגע כאן בשאלה די עמוקה, אפילו פילוסופית (שכבר נדושה כאן די הרבה) של האם האדם הוא בעל יכולת חישוב עדיפה על מכונת טיורינג. אם לא, אז הרי שאם באמת אפשר "לעבוד מאוד מאוד קשה ולמצוא את המעגל הרלוונטי", פירוש הדבר הוא שגם מכונת טיורינג יכולה לעשות זאת - דהיינו, מדובר על משפחה יוניפורמית של מעגלים (ומעגלים יוניפורמיים הם ללא ספק מודל חישובי רלוונטי ומרתק). אם האדם כן עדיף - כלומר, אם תראה שהמשפחה של המעגלים הללו היא אכן לא יוניפורמית (כלומר, אין מכונת טיורינג שמייצרת אותם) ותראה כי *למרות זאת* אפשר למצוא מעגל מכל גודל אם עובדים "מאוד מאוד קשה", זו סנסציה בפני עצמה - נראה לי שבמובן מסויים זה שובר את התזה של צ'רץ' וטיורינג. אני אישית מאמין בכל לבי שהאדם לא עדיף על מכונת טיורינג, כך שדוגמה כמו זו שאתה מתאר היא מראש פסולה מבחינתי כשמדובר על משפחות לא יוניפורמיות, ומכאן אולי הדוגמטיות שלי בנוגע ל"אמיתי". כמובן שייתכן שהאמונה שלי שגויה לחלוטין. |
|
|
|
|
|
|
||
|
||||
|
הטענה שלך לא נכונה, תחשוב על זה שוב. רמז: כל בעיה בגודל סופי היא כריעה. | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שאני מבין לאיזו טענה אתה מתכוון ומה הבעיה בגודל סופי. אם הבעיה היא "להפוך את ההצפנה" אז כן, זו בעיה סופית ובוודאי שיש מעגל שפותר אותה, ואפילו בוודאי שיש אלגוריתם שמייצר את המעגל הזה; אבל זה לא מבטיח שקיים אלגוריתם שעבור אינסוף אורכים שונים, יודע לייצר את המעגלים שמתאימים להם (כי הוא לא יכול "לזכור" את אופן ההתנהגות של אינסוף אלגוריתמים קטנים שכן התיאור שלו הוא סופי). הדבר דומה לכך שגם בעיית העצירה, כשמגבילים אותה למכונה ספציפית אחת על קלט ספציפי אחד, היא סופית ולכן "כריעה" - זה אומר ש*קיים* אלגוריתם שעונה את התשובה הנכונה (או האלגוריתם שאומר "כן" או זה שאומר "לא"), לא שאנחנו יודעים לגלות מהו. |
|
|
|
|
|
|
||
|
||||
|
בדיוק. ולכן... | |
|
|
|
|
|
||
|
||||
|
אני לא עוקב אחריך. או שאתה רוצה ללמד אותי משהו חדש, ואז אחלה, אבל תצטרך לפרט; או שאתה סתם רוצה לעשות ממני אידיוט, ואז אין צורך להתאמץ כל כך - רק צריך להגיד "הקבוצה המלאה" או משהו. | |
|
|
|
|
|
||
|
||||
|
לא הבנתי את החידוד בנושא "הקבוצה המלאה". בכל אופן, העניין הוא כזה (אני אשמח אם תסביר לי למה זה לא היה מובן מהודעתי הראשונה). קיום משפחת מעגלים אמנם לא אומר שיש תיאור סופי לפתרון הבעיה לכל קלט. לעומת זאת, לכל גודל קלט נתון, יש תיאור קטן (וזו הנקודה פה) לפתרון של הבעיה עבור אותו גודל. כלומר, אפשר לפתור את הבעיה עבור קבוצה של 2 בחזקת n קלטים בזמן פולינומי ב- n, זה ממש לא טריוויאלי וממש מעולה (או ממש גרוע, תלוי אם אתה המצפין או זה שמנסה לשבור את הצופן). בדרך כלל כשמבססים תקן על פרוטוקול הצפנה מסוים, קובעים את אורך המפתח התקני (או מספר קטן של אורכים מותרים). כיוון שיש משפחת מעגלים, לכל אורך שייבחר אפשר למצוא אלגוריתם יעיל אשר הופך את ההצפנה (אני מודה שהשימוש ב"לעבוד ממש קשה" לא רלוונטי פה ואולי קצת מטעה). יתר על כן, זו בעיה שאי-אפשר לתקן על ידי בחירת מפתח ארוך מספיק כיוון שכל אורך סובל מהבעיה הזו. |
|
|
|
|
|
|
||
|
||||
|
שוב, אם ל*כל* אורך אפשר היה למצוא את המעגל ששובר את ההצפנה, ובהנחה (שאתה מוזמן לחלוק עליה) שהאדם לא חזק חישובית ממכונת טיורינג, פירוש הדבר היה שמשפחת המעגלים הזו היא יוניפורמית. עזוב אותך לרגע מהצפנה. מדברים על השפה האונרית שבה כל מילה מייצגת קידוד של מכונת טיורינג+קלט, ובעיית ההכרעה שלנו היא לזהות בדיוק את אלו שעוצרות על המילה הריקה. האם קיים מעגל שפותר את הבעיה לכל אורך מילה אפשרי? (כמובן). האם, כשנותנים לנו אורך ספציפי, יש סיכוי שאם נעבוד ממש ממש קשה נצליח למצוא את התשובה, תמיד, לכל אורך? אם כן, האם לא פתרנו את בעיית העצירה? אם לא, מה ההבדל בין זה ובין הדוגמה הקריפטוגרפית? ("הקבוצה המלאה" היא תזכורת לימי דיון 1571 העליזים.) |
|
|
|
|
|
|
||
|
||||
|
אני מבין שאתה רוצה שאני אחלוק על ההנחה שלך אבל היא לא ממש רלוונטית לדיון שלנו. נשמע כאילו הבעיה שלך היא לא היוניפורמיות של האלגוריתם אלא הקונסטרוקטיביות שלו. באופן אנלוגי לפסקה השניה שלך, נגיד ש(כל) מה שאנחנו יודעים הוא שבעיה מסוימת היא ב- P. האם זה אומר שאם נעבוד מאוד קשה נמצא את האלגוריתם הפולינומי שפותר אותה? |
|
|
|
|
|
|
||
|
||||
|
אני לא מכיר מושג כזה, "קונסטרוקטיביות של אלגוריתם". בפרט אני לא רואה את ההבדל בינו ובין מה שאנחנו מכנים כאן בשם יוניפורמיות. אני לא בטוח אם קיימת הוכחה או לא לכך שמה שאתה מתאר בפסקה השנייה הוא בלתי כריע; איכשהו, נראה לי שהוא אכן כזה (דהיינו, אין אפילו אלגוריתם שמכריע בהינתן מכונת טיורינג האם היא פולינומית או לא - אולי אני טועה, ואולי יש לזה הוכחה טריוויאלית שאני לא חושב עליה כרגע). |
|
|
|
|
|
|
||
|
||||
|
אויש, אני כזה טמבל. מן הסתם לא קיים אלגוריתם שכזה וההוכחה אכן טריוויאלית (אם יש, נפתור את בעיית העצירה כך - בהינתן M ו-x, נבנה מכונה שעל כל קלט מריצה את M על x ועוצרת מייד אם M עצרה על x. היא פולינומית בגודל הקלט שלה אם ורק אם M עוצרת על x). | |
|
|
|
|
|
||
|
||||
|
קונסטרוקטיביות היא לא תכונה של אלגוריתם אלא של הוכחת/הנחת קיום. ההוכחה היא קונסטרוקטיבית אם היא מכילה את האלגוריתם באופן מפורש. | |
|
|
|
|
|
||
|
||||
|
"לעומת זאת, לכל גודל קלט נתון, יש תיאור קטן (וזו הנקודה פה) לפתרון של הבעיה עבור אותו גודל." - למיטב הבנתי, יש לך פה טעות קריטית. קיים תיאור סופי; הוא לא בהכרח קטן (עבור שום הגדרה שפויה של "קטן"). למעשה, גם עם המכונה היעילה ביותר שאפשר לדמיין, לא בהכרח יש לך מספיק אטומים ביקום. | |
|
|
|
|
|
||
|
||||
|
לי דווקא שאלת ה''קטן'' לא נראית רלוונטית בכלל לדיון, שעוסק בחישוביות ולא בסיבוכיות. | |
|
|
|
|
|
||
|
||||
|
הדוגמא שנתתי היא לגמרי דוגמא בסיבוכיות כך שהגודל כן חשוב. אולי נחזור רגע צעד אחורה וניזכר מה רציתי להראות בכלל. אני מנסה להסביר הוא למה המודל הלא יוניפורמי לא נראה לי "מופרך" (ברור שזו שאלה פילוסופית שלא ניתנת להוכחה, אבל אני יכול לנסות להסביר את תפיסת העולם שלי). אני אומר כך: נניח שבעיה מסוימת (שהמצאתי) אינה ניתנת לפתרון באופן יעיל (P או BPP) במודל מכונת טיורינג אבל ניתנת לפתרון באופן יעיל (P/poly) במודל לא יוניפורמי. אם המודל אכן היה "מופרך" (או נטול כל קשר לעולם הממשי), אז לעובדה שניתן לפתור את הבעיה באופן יעיל במודל ה"מופרך" לא היתה כל חשיבות והבעיה היתה נחשבת לבלתי פתירה בכל הקשר "אמיתי". בפועל, כיוון שבעולם הממשי (בהקשר של הבעיה שנתתי) התהליך הוא (ואני שוב חוזר לטרמינולוגיה קריפטוגרפית) שהיריב בוחר אורך קלט ומאותו רגע משתמש רק באורך הזה, העובדה שהבעיה פתירה ביעילות במודל לא יוניפורמי, מספיקה. |
|
|
|
|
|
|
||
|
||||
|
ניסיתי להתייחס לזה יותר בתגובה 481364, אבל אני חושב שאפשר לסכם את הכל במשפט אחד: למרות שהמודל עצמו מופרך, זה לא אומר ש*כל* מכונה שמתאימה למודל מופרכת. | |
|
|
|
|
|
||
|
||||
|
הסיפא של משפט הסיכום שלך טריוויאלית כיוון שהמודל הלא יוניפורמי הוא הכללה של המודל היוניפורמי (ששנינו מסכימים שאינו "מופרך"). הטענה שלי היא שתשובה שלילית לשאלה בתגובה 481378 פירושה שלמודל הלא יוניפורמי יש משמעות מעשית. האם הטענה שלך היא שהתשובה לתגובה 481378 חיובית או שהתשובה שלילית וזה עדיין לא מראה את מה שרציתי? |
|
|
|
|
|
|
||
|
||||
|
לדעתי השאלה שם די פשטנית, כי זה מאוד תלוי בצורה שבה יראו ש-RSA שייך לשם, והאם ניתן יהיה לתרגם אותה למשהו מעשי. כאמור, מכיוון ש-P/poly היא לא מעשית מעצם הגדרתה, אם משהו נמצא שם זה עדיין לא אומר שאי אפשר להשתמש בו, אלא רק שזה "מסוכן יותר". זו המהות של P/poly בתור חסם עליון - ההשלכה המעניינת האמיתית היא אם מראים שמשהו לא שייך לשם, ולכן הוא בטוח "מאוד". אבל אני חושב שהדיון קצת הלך לאיבוד - לא טענתי בשום מקום שאין עניין במודלים לא מציאותיים (הרי במכונת טיורינג אי דטרמיניסטית יש עניין רב - ואני לא מאמין שאפילו המודל הזה הוא מציאותי), אלא פשוט שהמודלים הללו מופרכים בכל הנוגע למחשבה על מימוש בפועל שלהם. |
|
|
|
|
|
|
||
|
||||
|
אז אתה כן רואה קונסטלציה מסוימת בה להיותה של בעיה ב- P/poly אך לא ב- BPP עשויה להיות השלכה מעשית (אפשר להתווכח על מידת ההשלכה אבל בפורמט זה יחס העלות/תועלת בדיון כזה נראה לי נמוך). זה כל מה שרציתי להגיד ובעיני זה מספיק כדי שהמודל לא יחשב "מופרך". אני דווקא חושב שהדיון לא הלך לאיבוד ודווקא עסק בדיוק בנושא שרציתי לדון בו. הטענה שלי היא לא שכל מודל מעניין מתמטית הוא בעל משמעות מעשית אלא ספציפית למודל של מעגלים לא יוניפורמיים. אני די מסכים עם הטענה שלך שמכונת טיורינג לא דטרמיניסטית היא "סתם" טריק מתמטי. אפילו בתיאוריה של סיבוכיות כבר לא משתמשים (כמעט) בהגדרה של מכונה לא דטרמיניסטית, אלא בהגדרה השקולה של קיום מוודא (דטרמיניסטי). |
|
|
|
|
|
|
||
|
||||
|
קיום מוודא דטרמיניסטי לא הופך את המודל של NP למופרך פחות, כי ההוכחה צריכה לבוא ממקום כלשהו, וב"עולם האמיתי" אין כזה מקום באופן כללי. כמובן שבמקרים פרטיים יש כזה מקום (נניח, אתה יודע פירוק של מספר כי אתה חישבת אותו מלכתחילה על ידי הגרלת ראשוניים והכפלתם) ואז התיאור של NP מתאים, אבל באופן כללי אין, ומכאן ה"מופרכות". | |
|
|
|
|
|
||
|
||||
|
אוי. חבל שאתה מנסה להתווכח עם דברים שלא כתבתי. כתבתי שמכונת טיורינג לא דטרמיניסטית היא ''סתם'' טריק מתמטי ולא שמוודא דטרמיניסטי אינו כזה. עוד יותר חבל בגלל שמוודא דטרמיניסטי זה דווקא משהו שאני ואתה עושים כל הזמן. כל פעם שאתה קורא ספר או מאמר ו''מבין'' (כלומר בודק) את ההוכחות המופיעות בו, אתה למעשה משמש כמוודא דטרמיניסטי. תרגיש חופשי להגיב למה שכתבתי אבל, ברשותך (או שלא ברשותך), אני לא מתכוון לענות. אני מרגיש שבינתיים סיימתי את תפקידי ההיסטורי בדיון הזה. שלא לדבר על כך שמישהו כבר ביקש ממני לבחור כינוי והמחויבות קצת מלחיצה אותי (לא באמת). אולי אם ממש יבער לי אני אשוב. |
|
|
|
|
|
|
||
|
||||
|
אני לא מנסה להתווכח. אני מנסה להגיע להסכמה דווקא. קיוויתי שברור מההודעה הקודמת שלי שאין לי בעיה עם הרעיון של המוודא אלא עם המקור של ההוכחה, כלומר עם העובדה שהמודל החישובי הכולל של NP דורש גם מקום שממנו ההוכחה תבוא, וכזה מקום באופן כללי אין. | |
|
|
|
|
|
||
|
||||
|
1. כשמדברים על העולם האמיתי, כמו שאנחנו עושים כרגע, פולינומי בגודל הקלט איננו ראוי בהכרח לתואר "קטן". 2. למיטב הבנתי, לא כל סדרה לא-יוניפורמית של מעגלים מקיימת שכל מעגל בעל יצוג באורך פולינומי במספר הסידורי שלו. זו נקודה שלא ראיתי אצלך אתמול בהודעות, אבל כן היום כששאלת "תכל'ס, אם יוכיחו ש-RSA ב-P/Poly" וכו', אז לא משנה. 3. אודה לך אם תבחר כינוי זמני. בינתיים עוד לא הצטרף אלמוני נוסף לדיון, אבל זה יכול לקרות כל רגע. |
|
|
|
|
|
|
||
|
||||
|
הצפנה עם סודיות מוחלטת דורשת כתנאי הכרחי החלפת מפתחות מראש, ומפתח שאיננו קצר מההודעה המוצפנת. זה הופך אותה ללא-רלוונטית בתחומים רבים, אבל בתחומים שהיא כן רלוונטית, מכונה כמו שתיארת (דמיונית לחלוטין - אני כאן עם גדי לגמרי) לא פוגעת בסודיות בכלל. הצפנה ללא סודיות מוחלטת חשופה מפני מכונות טיורינג (דמיונית) לאותן התקפות כמו המכונה האפילו יותר דמיונית שלך (שמסוגלת לחשב בזמן קבוע, אבל נדרש זמן יותר [הרבה יותר] מפולינומי באורך המפתח לבנות אותה - ויותר חשוב, למספר אטומים העולה על זה שנמצא ביקום, כבר לקלטים באורך לא גדול במיוחד - זאת מבלי בכלל להכנס לזמן האסימפטוטי). דרך אגב, לתוך כל הצפנה ראויה לשמה מובנה אלמנט של אקראיות (למיטב זכרוני, זה לא פרט אמפירי, אלא מוכח על ידי משפטים [לגבי הטענות הקודמות בהודעה שלי - אני זוכר כמעט בוודאות שהן מוכחות על ידי משפטים]), כך שבכל מקרה, אתה לא לומד בוודאות מה הייתה ההודעה שהוצפנה, אלא יכול פשוט להבדיל בין שני פענוחים אפשריים בהסתברות הגדולה מחצי באופן לא-זניח (אך למטרות פרקטיות - שהינו פעמים רבות נמוך). דיסקליימר: 1. את המועד ב' בקורס בקריפטוגרפיה אני עושה ביום חמישי, ועוד לא הספקתי לעבור מחדש על החומר. 2. השעה כרגע ארבע לפנות בוקר. 3. שתיתי. |
|
|
|
|
|
|
||
|
||||
|
זה נושא מעניין, אז אנסה להרחיב עליו, מהמעט שלמדתי: לא טריוויאלי להגדיר בטיחות של סכמת הצפנה - באותה סכמת הצפנה עשויה להשתמש בסיטואציות שונות (מצפינים אחת מתוך קבוצה קטנה של הודעות ידועות מראש [כן/לא, עכשיו/מחר], קבוצה גדולה [ספרים שכתובים באנגלית ושמורים בפורמט ידוע] או כל הודעה אפשרית?), בצורות שונות (שולחים עוד הודעות שמוצפנות באותו המפתח?), התוקף את ההצפנה עשוי להשתמש בכלים שונים (שהגדרת הבטיחות צריכה לקחת בחשבון את כולם, מבלי להניח מראש מה הם, לפני שהיא נותנת את חותמת הכשרות), וכן הלאה. הכי חשוב - מה נחשב לנפילה של סכמת ההצפנה? אם התוקף יודע שאותו המסר נשלח פעם שניה, האם זה כשלון? בסיטואציות מסויימות כן (למשל, אם ראינו שהמשחתת חזרה לנמל, סביר שזה גם מה שיקרה בפעם הבאה שתקבל את אותו המסר), באחרות לא (העותק של הארי פוטר נשלח לשני אנשים שונים בחברה המוציאה לאור? איך זה עוזר לי להתחיל להדפיס עותקים פיראטיים בסין?). וזו רק דוגמה אחת (אחרות: אורך ההודעה? היוניפורמיות של התוכן? שפת התוכן? האם התוכן הוא קידוד של תמונה כלשהי, טקסט באנגלית או קובץ וידאו? דמיון כלשהו להודעה קודמת [מתנהל משא ומתן על משכורת?]?). אז יש כמה מודלים בסיסיים שסכמת הצפנה עשויה להיות בטוחה עבורם או לא. ביניהם - הצפנה חד-פעמית, הצפנה רב-פעמית, הצפנה שבה לתוקף יש אפשרות, מבלי לדעת את המפתח, לבקש ולקבל הצפנה של מסר לבחירתו באמצעות אותו המפתח (מן הסתם יש כמה וריאנטים לכל אחד מאלה, אבל אני למדתי רק וריאנט אחד של כל אחד מאלה, והם נשמעו לי מוצלחים, אז אני מאמין שהם סטנדרטים שמקובלים על הרוב). בכדי להניח את המינימום האפשרי על צרכי התוקף ומה שמהווה עבורו שבירה של ההצפנה, מאמצים עמדה פסימית במיוחד - הצפנה חד-פעמית נחשבת כשבורה אם תוקף יכול לבחור שתי הודעות, ואז אחת מהן - הוא לא יודע איזו - מוצפנת, והוא מסוגל לנחש, בהנתן ההצפנה, איזו משתי ההודעות שלו הוצפנה. ההיגיון - אם אפילו כשהוא בוחר את ההודעות בעצמו, אף תוקף לא יכול להבחין, אז הרי שהסכימה טובה לכל הודעה תחת כל התקפה. כל מידע שהוא עשוי לרצות לשלוף מההודעה - שפת התוכן, מספר הפעמים שמופיעה האות ג' - אם אפשר היה לשלוף מהקובץ המוצפן, הרי שהוא יכל לבקש להצפין שתי הודעות שנבדלות בתכונה הזאת, ובאמצעות הדרך שכביכול יש לו לשליפת המידע הזה מהקובץ המוצפן, יכל היה להבחין איזו משתי ההודעות שבחר הוצפנה. אם נצליח להוכיח שאף תוקף (הגדרת התוקף מכילה בתוכה את זוג ההודעות שיבחר) לא מסוגל להבחין[*], הרי שהסכמה בטוחה. עכשיו, לגבי מה שאמרתי מקודם בקשר לכך שכל הצפנה ראויה לשמה מכילה אלמנט של אקראיות - המבחן לבטיחות של סכמת הצפנה שמתיימרת להיות בטוחה גם אם משתמשים בה, עם אותו המפתח, מספר פעמים, היא שהתוקף בוחר שני רצפים של הודעות, אחד מהרצפים מוצפן (כל הודעה ברצף מוצפנת בנפרד, אבל עם אותו המפתח) והצפנתו מוחזרת לתוקף, והוא אמור לנחש איזה משני הרצפים הוצפן. אם אין אלמנט של אקראיות, הרצה של אלגוריתם ההצפנה פעמיים על אותו הקלט תיתן את אותה התוצאה, ולכן התוקף יכול פשוט לתת רצף אחד שמורכב משתי הודעות שונות, ורצף שני שמורכב מאותו הודעה פעמיים, ובצורה זו להבחין איזה מהרצפים הוצפן - אם שתי ההודעות ברצף ההצפנה המוחזר לו זהות, זה השני, ואחרת, זה הראשון. באופן טריוויאלי, כל סכמת הצפנה שתהיה בטוחה להצפנות חוזרות ונשנות, חייבת להכיל אלמנט של אקראיות, כך שהצפנה כפולה של הודעה תיתן [בהסתברות גבוהה] תוצאות שונות (וכך, כמובן, לא ידע התוקף כשהודעה נשלחה פעמיים). (באופן דומה לגבי המודל השלישי - אם התוקף יכול לבחור מה להצפין, הוא יכול לבחור להצפין שוב את ההודעה הראשונה, ובמידה והיא זהה להצפנה שקיבל, זו ההודעה שלו שהוצפנה, ואחרת, זו השניה.) דוגמה לניסיון של ההגדרה להמנע מהנחות לגבי *יכולותיו* של התוקף - המודל השלישי שהזכרתי מדבר על תוקף שיש לו אפשרות לקבל הצפנה של הודעות לבחירתו. זה לא מצב סביר במיוחד, אבל זה מידול פסימי מאוד (ולכן מצויין) של יכולות שקשה מאוד למדל אחרת של תוקף בעולם האמיתי להשפיע על המתקשרים באופן מוצפן והמידע העובר ביניהם, ולהשתמש בכך לשם פיענוח התקשורת ביניהם. דוגמה דבילית משהו, אבל קצרה - אם יש לי את האפשרות להאט את התקשורת בין המתקשרים באופן מוצפן, אני עשוי לגרום למשפט "אני סובל מאיטיות בתקשורת" להתווסף לשיחה. איך נמדל השפעה שכזאת כשאנחנו מנסים להוכיח שסכמת הצפנה בטוחה? איך נתייחס לאינספור האפשרויות הנוספות? הכי פשוט ויעיל למדל את ההשפעה המירבית שיכולה להיות לתוקף - הוא קובע את *כל* מה שיאמר בהודעה אחת שמוצפנת עם אותו המפתח - ואם הסכמה בטוחה אפילו בפני זה, היא כמובן בטוחה בפני השפעות חלשות יותר, כמו העלאת הסיכוי שאומר משהו ספיציפי, ושימוש שלו במידע הזה להסקת המפתח. --- * היות ותמיד אפשר להטיל מטבע, ב"לא יכול לנחש איזו משתי ההודעות שבחר הוצפנה", הכוונה הייתה שלא יכול לעשות זאת עם הסתברות להצלחה גדולה מחצי (במקרה של סודיות מושלמת) או גדולה משמעותית מחצי (במקרה של סודיות חישובית - אותה אנסה להסביר רק אם מישהו רוצה). --- מי שהנושא מעניין אותו, יכול לקרוא יותר בספר הבא - http://www.amazon.com/Introduction-Cryptography-Chap... אני מקווה שהסברתי מעט מהנושא עם מינימום טעויות ובאופן סביר, ושהודעתי לא עושה שירות דוב למחברי הספר. |
|
|
|
|
|
|
||
|
||||
|
אין טעם להסתבך ולהתפלפל. בוא נהיה קונקרטיים: אם היו מוכיחים ש- RSA לא ב- BPP אבל כן ב- P/poly, האם היו ממשיכים להשתמש בו? | |
|
|
|
|
|
||
|
||||
|
למה לא? במה שונה עיבוד שדורש זמן לא-פולינומי לפני שההודעה אפילו נכתבה (ובטח שהוצפנה), מעיבוד שדורש זמן לא-פולינומי רק אחרי שהוצפנה ונשלחה? שני המקרים לא-סבירים כמעט באותה המידה (והאינטואיציה אומרת שיהיה יותר קל - סליחה, פחות קשה - לבצע דווקא את הראשון). חוץ מזה, כל עוד אין לך אלטרנטיבה שאיננה ב-P/Poly, צריך להשתמש במשהו, לא? |
|
|
|
|
|
|
||
|
||||
|
לא בהכרח - את העיבוד המקדים צריך לבצע רק פעם אחת, ואחר כך אפשר יהיה להשתמש בתוצאותיו הרבה פעמים, כך שמן הסתם אנו מתירים לו להיות כבד יותר (כך זה תמיד עם אפליקציות שמבוססות על עיבוד מוקדם). לדוגמה, נניח שיגלו שבהינתן פקטוריזציה של מספר פריק *כלשהו* בן 500 ספרות אפשר לפקטר *כל* מספר בן 500 ספרות (כן, מופרך, אבל זו דוגמה), אז ינבע מכך ש-RSA היא ב-P/poly, ואנשים ישמחו מאוד להפעיל את ה-Number field sieve בגרסה אולטרה ממוקבלת ברשת שתדרוש אולי חודש ריצה אבל תחסל את תקן ה-RSA הנוכחי (נניח שהוא בן 500 ספרות...). |
|
|
|
|
|
|
||
|
||||
|
לא בהכרח מה? אמרתי "סבירים כמעט באותה המידה" - למרות ה"כמעט" אתה לא מסכים? שים לב שאני מדבר על סבירות ההצלחה, ומוכן לצאת מנקודת ההנחה שמקדישים את כל מה שרק אפשר, בלי התחשבות בתועלת הצפויה. הרי בשני המקרים נדרשים משאבים שאנחנו אפילו לא יכולים להתקרב אליהם. אז מה זה משנה אם יש לנו נכונות להשקיע יותר ממה שממילא לא קרוב אפילו למספיק במכונה היותר כללית? "לדוגמה, נניח שיגלו שבהינתן פקטוריזציה של מספר פריק *כלשהו* בן 500 ספרות אפשר לפקטר *כל* מספר בן 500 ספרות (כן, מופרך, אבל זו דוגמה), אז ינבע מכך ש-RSA היא ב-P/poly" - במקרה הלא סביר הזה, למי בכלל אכפת מ-P/poly? הרי הבעיה כבר ב-BPP במקרה הזה, לא? את המשך אותה פסקה, דרך אגב, לא הבנתי. אולי גם לא את מה שלפני. |
|
|
|
|
|
|
||
|
||||
|
זהו, שניסיתי להמחיש עם הדוגמה שלא מדובר באותה "מידה" של סבירות. הנקודה המהותית היא שאם צריך למצוא "רמז" רק פעם אחת, אז למרות שההשקעה היא מטורללת אפשר להגיע אליה, בעוד שלהגיע לאותה רמת השקעה ב"יום יום" זה לא סביר. הבעיה לא בהכרח ב-BPP אם מתקיים מה שתיארתי. אתה עדיין צריך "רמז" בשביל כל גודל מספר, והחישוב של הרמז הוא עדיין קשה. |
|
|
|
|
|
|
||
|
||||
|
מפתיע אותי וכלל לא ברור לי למה אתה אומר על ההשקעה שאתה בעצמך הגדרת הרגע כמטורללת, בהנחה ששנינו חושבים על אותו סדר גודל, כ"אפשר להגיע אליה". על איזה רמז אתה מדבר? מה הבעיה למצוא את הפירוק של מספר כלשהו בן חמש-מאות ספרות (נגיד בינאריות)? פשוט מכפילים שני ראשוניים ששניהם בני 250 ספרות1, והרי לך מספר פריק בן 500 ספרות ופירוקו. --- 1 בערך. לא נתעכב על זה. |
|
|
|
|
|
|
||
|
||||
|
טוב, בטח התכוונת שקיים אחד ספיציפי כזה, אבל לא ידוע מי הוא. אז: 1. מאוד קשה לי לדמיין את זה (אבל כבר אמרת שגם לדעתך זו דוגמה מאוד מופרכת). 2. אני אניח שאתה מתכוון גם שלכל אורך, המספר הזה הוא שונה. אם אפשר למצוא את המספר הזה בזמן פולינומי, הרי שזו סדרה יוניפורמית (כמו שאמרת בעצמך לאלמוני), והבעיה ממילא ב-BPP. אם אי-אפשר בזמן פולינומי, החל מגודל מסוים, אי-אפשר לפני קץ היקום ובהסתברות ראויה לציון גם אם נשקיע את כל המשאבים שבעולם, אבל עדיין אפשרי לחבר'ה הישרים להשתמש בסכמה במשאבים סבירים (נו, כנראה. לא ידועים לי הקבועים של RSA, ואתה ממילא יכול להעביר את הדיון לכל סכמת הצפנה אחרת ונשאר עם אותו הפרנציפ), ואז מה אכפת לנו שיש גם את ההתקפה הלא-אפשרית הזאת על ההצפנה? אני חוזר על השאלה המקורית שלי - אם גם עם כל המשאבים שאפשר לדמיין אי-אפשר, מה זה משנה לי שיש גם נתיב התקפה שבו מישהו עשוי להיות יותר נכון להשקיע את המשאבים האלו? הם הרי עדיין לא מספיקים. |
|
|
|
|
|
|
||
|
||||
|
הכוונה הייתה שאפשר למצוא את המספר בזמן פולינומי, לא את הפירוק שלו. מאוד אכפת לנו שיש את ההתקפה הלא-אפשרית הזו על ההצפנה כי קיומה *מכריח* אותנו להגדיל את הקבועים שבהם אנחנו משתמשים. אם פתאום ניאלץ, במקום להשתמש ב-RSA של 2048 סיביות, להשתמש בכזה של 32768, זה מעיד על שינוי מהותי שההתקפה הלא-אפשרית גרמה. |
|
|
|
|
|
|
||
|
||||
|
סלח לי, לא הבנתי - להגדיל את הקבועים נאלצים מדי פעם, אבל מה הנקודה? | |
|
|
|
|
|
||
|
||||
|
כי אפשר, אם אתה לא עובד עם מחשב יחיד אלא עם עשרות אלפי מחשבים, ומוכן להשקיע פרק זמן שבדרך כלל היה נחשב בעינייך לא סביר. הרי בימינו *מצליחים* לפרק לגורמים מספרים, זה פשוט קשה. בקשר לפירוק - אה, כן, צודק, דוגמה גרועה. אבל זה הרעיון שחשוב. נסה לשחזר את הדוגמה שלי עם משהו שאי אפשר לייצר בקלות (או לחילופין, עם "צריך פירוק של מספר ספציפי שקל למצוא אותו אבל הפירוק שלו לא ידוע). |
|
|
|
|
|
|
||
|
||||
|
כל העניין בבעיות עם סיבוכיות לא-פולינומית, הוא שאפילו עם מיליארדי מחשבים, אי-אפשר לפתור מופעים גדולים מספיק שלהם. זה שמצליחים לפרק מספרים, אתה בוודאי יודע, זה ממש לא מרשים - אני יכול לפרק חלק בראש; גדולים יותר אפשר עם עשרות אלפי מחשבים; גדולים מספיק, במידה ובעיית הפירוק אכן לא פולינומית, אי-אפשר יהיה גם אם כל אטום בודד ביקום יהיה מעבד מרובה ליבות. אני בוודאי לא צריך להזכיר לך זאת, אבל לא יזיק שיופיע בפרוטוקול - גם עם בעיות ליניאריות, יש מופעים שאי-אפשר לפתור לפני מות היקום עם מיליארדי מחשבים. החלק המעניין, לצרכי קריפטוגרפיה, הוא שהשחקנים הישרים עדיין יכולים לפעול בזמן סביר, בעוד שלתוקף אין שום דרך מלבד זו הדורשת את המשאבים שאין, ולעולם לא יהיו, בנמצא. אני רוצה לחזור על הנקודה שלי, שנדמה לי (סלח לי) שהיא נכונה, פשוטה, ושחמקה ממך באופן מפתיע עד עכשיו (או שאתה מנסה לדבר על משהו אחר, ואני זה שמתבלבל) - יהי סט של בעיות שאפשר לפתור כל אחת מהן בנפרד, או את כולן ביחד. אתה אומר - יש יותר אינטרס לאנשים להשקיע בפתרון הכללי שפותר את כולן ביחד. אני אומר - כל עוד לא זה אפשרי ולא זה אפשרי - בכלל - מידת האינטרס לא משנה. בלתי-אפשרי נשאר בלתי-אפשרי גם אם עובדים בצוות. "נסה לשחזר את הדוגמה שלי עם משהו שאי אפשר לייצר בקלות" - עזור לי בבקשה. |
|
|
|
|
|
|
||
|
||||
|
העניין של "גדולים מספיק אי אפשר גם אם כל אטום ביקום יהיה מעבד מרובה ליבות" נכון, כמובן, גם לדברים עם סיבוכיות פולינומית, כך שאני מציע שתזנח לרגע את גישת ה"אם משהו הוא לא פולינומי, אין שום סיכוי לחשב אותו". הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק. אנסה לחדד את הנקודה. אני מבדיל בין שלושה סוגי חישובים - כאלו שהם בלתי פיזיביליים בכלל, ועליהם לא מדברים; כאלו שהם קלים וכל מחשב ביתי עושה בצורה זריזה (לצורך הדיון, אלו הפולינומיים); וכאלו שהם "בינוניים" - במחשב ביתי זה ייקח יותר מדי זמן, אבל אם כל המחשבים בעולם יתאגדו וישתפו פעולה, ויחכו חודש חודשיים, החישוב יסתיים. עכשיו, בוודאי שיש הבדל מהותי בין הסיטואציה שבה בכל פעם שרוצים לפרוץ הודעה צריך לבצע חישוב "בינוני" שכזה, ובין הסיטואציה שבה מספיק שכל העולם יבצע פעם אחת את החישוב ה"בינוני" ואז כל אחד יוכל לפרוץ בקלות הודעות קצרות מספיק. המשמעות של זה פשוטה, והיא זו שניסיתי להסביר בהודעה האחרת שאליה הגבת - אם בעיה כלשהי היא כרגע בטווח ה"בינוני", אז למרות שהאלגוריתם שפותר אותה הוא אקספוננציאלי ואפשר להפוך אותה לבלתי אפשרית על ידי הגדלת פרמטר הבטיחות של ההצפנה, בכל זאת היא תגרום לנו לעשות משהו מעשי מאוד - להגדיל את פרמטר הבטיחות של ההצפנה, אולי בצורה לא טריוויאלית, בטח בקפיצה שלה לא ציפינו. הסיבה שבגללה פרמטר הבטיחות גדל בדרך כלל היא שהפתרון הנאיבי (שגם הוא לא פיזיבילי בהינתן פרמטר גדול מספיק) מתחיל להיות מאיים - ולכן גם אלגוריתמים לא יעילים אחרים מסוגלים להיות מאיימים. |
|
|
|
|
|
|
||
|
||||
|
(אמרתי בעצמי שגם לליניארי זה נכון עבור ערכים מסויימים. הסברתי למה עבור ליניאריים זה לא מעניין, ועבור לא-פולינומיים כן - כי השחקנים הישרים נשארים בזמן סביר.) "הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק." - זו לא נקודה מעניינת, כי, לאור הפסקה הקודמת שלי, אין שום סיבה שלא לבחור בהצפנה דווקא את סט הערכים שאינם נמוכים מספיק. (כלומר, יש יתרונות לכך - הצפנה בשניות במקום בשעות - אבל זה לא מחויב המציאות. במידת הצורך, יהיה אפשר לעשות את ההקרבה הזאת, ולהשיג שוב סודיות טובה, במחיר הנוחות של הצפנה כמעט-מיידית.) -- כלומר, הנקודה שלך לאורך הדיון הייתה שיש תרחישים שבהם התקדמות אלגוריתמית דורשת הגדלה של קבוע הבטיחות הנפוץ בהצפנה? מן הסתם אני מסכים. |
|
|
|
|
|
|
||
|
||||
|
בדיוק. אם בגלל איזו תגלית תיאורטית שמעידה על תוצאה ''בלתי אפשרית'' לכאורה גורמת לצורך להצפין בשעות במקום בשניות - כנראה שבכל זאת מדובר במשהו בעל השלכות מעשיות. | |
|
|
|
|
|
||
|
||||
|
קראתי עוד טיפה. נראה לי שהשימוש הזה של P/poly בקריפטו הוא חלק ממגמת הפיכת היריב ל"כל יכול" שנפוצה בה כדי להבטיח, גם תיאורטית, שאפשר להתגונן מפניו - בדומה, נניח, לאיך שבהוכחות אפס-ידע אנחנו לא מניחים שום מגבלה על יכולת החישוב של המוכיח. זה כמובן לא אומר שמדובר על מודל "מעשי"; אבל זה כן אומר שמדובר במודל שתופס *גם* את כל מה שאנחנו מבינים בתור "מעשי", ולכן הגנה בפניו בפרט מבטיחה (באופן מוחלט, לא אד-הוקי) הגנה בפני כל תוקף ממשי. במקרה של P/poly, היא מספקת הגנה מפני מישהו שיבצע עיבוד מקדים מסובך (*כן* ניתן לחישוב, אבל אולי לא פולינומי) שיסייע לו בתקיפת מערכת ההצפנה אחרי שהוא יתחיל לראות הודעות. העיבוד המקדים יבוא לידי ביטוי ב"רמזים". כך אפשר להתגונן נגד יריב שהוא קצת יותר מ-P או BPP סטנדרטי; אבל עד כמה שאני מבין, אין במחשבה הפרקטית הזו התייחסות לאספקטים הלא כריעים של P/poly, כלומר היה אפשר לצורך השימוש הזה להצטמצם למחלקה קטנה יותר ואולי יוניפורמית, אבל מכיוון שזה כנראה יסבך את ההגדרות וההוכחות אין בכך טעם. |
|
|
|
|
|
|
||
|
||||
|
אני אמנם לא מתמצא במיוחד במודלים לא יוניפורמיים, אבל אתה יכול לתת דוגמא לשימוש במודל כזה בהקשר של חישוביות ולא של סיבוכיות. כי נראה לי שכל המודלים הללו הם טריוויאליים מבחינת החישוביות (דהיינו, הכל חשיב בהם). | |
|
|
|
|
|
||
|
||||
|
הכל? בהחלט לא, כי מגבילים את גודל ה"רמז" שהמכונה מקבלת להיות פולינומי. הדוגמה הקלאסית היא המחלקה P/poly (מכונה פולינומית/רמז פולינומי לכל גודל קלט) שמכריעה שפות לא כריעות ולכן מהווה מודל "דמיוני", אבל לא מסוגלת להכריע כל דבר, ולכן עדיין מעניינת (בתור "חסם עליון" על מה שכן אפשר להכריע, כי היא מכילה את BPP). |
|
|
|
|
|
|
||
|
||||
|
תודה, אבל זה עדיין רמאות: כמו לקרוא ל- P מודל חישובי. | |
|
|
|
|
|
||
|
||||
|
זה דומה, אבל אני לא מסכים שזה זהה (כאן זו שאלה של גודל התיאור, לא של כמה משאבים אנחנו מרשים למכונה לצרוך). מצד שני, מדובר כאן על הבדל שהוא פילוסופי בעיקרו ואנחנו ממילא באותו צד אז לא נריב. | |
|
|
|
|
|
||
|
||||
|
זה נכון. צריך להגדיר טיפה יותר טוב מה זה ''המודלים האלו'' ומה זה אומר ''הכל חשיב בהם''. אם אתה מרשה מעגלים בגודל אקספוננציאלי מספיק גדול או לחילופין קלט בייצוג אונארי, אכן הכל חשיב. הדוגמא שנתתי באמתת מסתמכת על מחלקת סיבוכיות המוגדרת באמצעות המודל הזה. |
|
|
|
|
|
|
||
|
||||
|
לטעמי, לפחות במקרה הזה ניתוח מתמטי חמור של טענת טיורינג אינו מתאר באופן מספיק את היופי הפרקטי שלה. יש מספיק בעיות שגם אדם שאינו מתמטיקאי ואינו מוטרד אם למונחים פתרון אפקטיבי/פתרון חישובי /חישוביות אפקטיבית יש הגדרה תקפה ולא אינטואיטיבית, מבין מה הוא סוג הפתרון הנדרש לבעיה (למשל בעיית הריצוף). היופי שאני רואה בטענת טיורינג מתבטא גם בניסוח הכי חלש ולא מדוייק שלה, שאני יכול להעלות על הדעת: ישנן בעיות שאם מחשב כלשהו מסוגל לפתור אותן, הרי שזהו מחשב מאוד מאוד שונה מהמחשבים שאנו מכירים וחושבים עליהם. |
|
|
|
|
|
|
||
|
||||
|
זה ניסוח לא רע, לדעתי, המתאים למאמר מהסוג הזה. השווה עם הניסוח ''מסקנה זאת הינה מפתיעה כשלעצמה, במיוחד כיום, כשרבים מאיתנו סבורים שמחשבים יכולים לבצע כל פעולה חישובית.'' | |
|
|
|
|
|
||
|
||||
|
אני אנסה לכתוב את ההוכחה בקצרה תוך שימוש בטרמינולוגיה של תוכניות מחשב ולא של מכונות טיורינג (מכונת טיורינג אוניברסלית שקולה למחשב הניתן לתכנות). משפט: לא קיימת תוכנית מחשב A אשר מקבלת שני קלטים: תוכנית מחשב Y וקלט x עבור Y, ומחזירה "כן" אם ריצת Y על x עוצרת ו"לא" אם לא. הוכחה: נניח שקיימת A כזו. נכתוב תוכנית חדשה B המקבלת כקלט תוכנת מחשב Z. התוכנית B מריצה את התוכנית A על הקלטים Y=Z,x=Z. אם הפלט של A על קלטים אלה הוא "כן", התוכנה B נכנסת ללולאה אינסופית. אם התשובה של A היא "לא", התוכנה B עוצרת (ומחזירה, נניח, "כן"). עכשיו בואו נראה האם הרצת B עם Z=B עוצרת או לא. נניח בהתחלה שכן ונתבונן בפרטי החישוב: קודם כל מריצים את A עם Y=B,x=B, כלומר בודקים אם B עוצרת עם Z=B, מכיוון שאנחנו מניחים ש- A פועלת כהלכה, היא צריכה להחזיר "כן" ואז B נכנסת ללולאה ולא עוצרת בסתירה להנחה שלנו. עכשיו בואו נניח ש- B לא עוצרת על B. במקרה כזה הרצת A אמורה להחזיר "לא" ונקבל ש- B כן עוצרת, שוב בסתירה להנחה. מכאן שלא קיימת A כפי שהנחנו. |
|
|
|
|
|
|
||
|
||||
|
...וכפי שרואים, את אותה ההוכחה בדיוק אפשר להחיל על כל מודל חישובי באשר יהיה, כל עוד הוא תומך במספר פעולות בסיסיות (כמו "היכנס ללולאה אינסופית" או "קרא לתוכנית A עם קלט X"). מכאן שהטענה "לא ניתן לפתור את בעיית העצירה" היא רחבה מאוד (כלומר, אינה תקפה דווקא למכונות טיורינג) ואין לה צורך להסתמך על התיזה של צ'רץ'-טיורינג. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |