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