בתשובה לגדי אלכסנדרוביץ', 12/06/08 22:06
 |
|
 |
||
|
||||
 |
הטענה שלך לא נכונה, תחשוב על זה שוב. רמז: כל בעיה בגודל סופי היא כריעה. |  |
 |
 |
|
|
|
||
|
||||
|
אני לא בטוח שאני מבין לאיזו טענה אתה מתכוון ומה הבעיה בגודל סופי. אם הבעיה היא "להפוך את ההצפנה" אז כן, זו בעיה סופית ובוודאי שיש מעגל שפותר אותה, ואפילו בוודאי שיש אלגוריתם שמייצר את המעגל הזה; אבל זה לא מבטיח שקיים אלגוריתם שעבור אינסוף אורכים שונים, יודע לייצר את המעגלים שמתאימים להם (כי הוא לא יכול "לזכור" את אופן ההתנהגות של אינסוף אלגוריתמים קטנים שכן התיאור שלו הוא סופי). הדבר דומה לכך שגם בעיית העצירה, כשמגבילים אותה למכונה ספציפית אחת על קלט ספציפי אחד, היא סופית ולכן "כריעה" - זה אומר ש*קיים* אלגוריתם שעונה את התשובה הנכונה (או האלגוריתם שאומר "כן" או זה שאומר "לא"), לא שאנחנו יודעים לגלות מהו. |
|
|
|
|
|
|
||
|
||||
|
בדיוק. ולכן... | |
|
|
|
|
|
||
|
||||
|
אני לא עוקב אחריך. או שאתה רוצה ללמד אותי משהו חדש, ואז אחלה, אבל תצטרך לפרט; או שאתה סתם רוצה לעשות ממני אידיוט, ואז אין צורך להתאמץ כל כך - רק צריך להגיד "הקבוצה המלאה" או משהו. | |
|
|
|
|
|
||
|
||||
|
לא הבנתי את החידוד בנושא "הקבוצה המלאה". בכל אופן, העניין הוא כזה (אני אשמח אם תסביר לי למה זה לא היה מובן מהודעתי הראשונה). קיום משפחת מעגלים אמנם לא אומר שיש תיאור סופי לפתרון הבעיה לכל קלט. לעומת זאת, לכל גודל קלט נתון, יש תיאור קטן (וזו הנקודה פה) לפתרון של הבעיה עבור אותו גודל. כלומר, אפשר לפתור את הבעיה עבור קבוצה של 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. אודה לך אם תבחר כינוי זמני. בינתיים עוד לא הצטרף אלמוני נוסף לדיון, אבל זה יכול לקרות כל רגע. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |