בתשובה להאייל האלמוני, 14/06/08 12:50
 |
|
 |
||
|
||||
 |
לדעתי השאלה שם די פשטנית, כי זה מאוד תלוי בצורה שבה יראו ש-RSA שייך לשם, והאם ניתן יהיה לתרגם אותה למשהו מעשי. כאמור, מכיוון ש-P/poly היא לא מעשית מעצם הגדרתה, אם משהו נמצא שם זה עדיין לא אומר שאי אפשר להשתמש בו, אלא רק שזה "מסוכן יותר". זו המהות של P/poly בתור חסם עליון - ההשלכה המעניינת האמיתית היא אם מראים שמשהו לא שייך לשם, ולכן הוא בטוח "מאוד". אבל אני חושב שהדיון קצת הלך לאיבוד - לא טענתי בשום מקום שאין עניין במודלים לא מציאותיים (הרי במכונת טיורינג אי דטרמיניסטית יש עניין רב - ואני לא מאמין שאפילו המודל הזה הוא מציאותי), אלא פשוט שהמודלים הללו מופרכים בכל הנוגע למחשבה על מימוש בפועל שלהם. |
 |
 |
 |
|
|
|
||
|
||||
|
אז אתה כן רואה קונסטלציה מסוימת בה להיותה של בעיה ב- P/poly אך לא ב- BPP עשויה להיות השלכה מעשית (אפשר להתווכח על מידת ההשלכה אבל בפורמט זה יחס העלות/תועלת בדיון כזה נראה לי נמוך). זה כל מה שרציתי להגיד ובעיני זה מספיק כדי שהמודל לא יחשב "מופרך". אני דווקא חושב שהדיון לא הלך לאיבוד ודווקא עסק בדיוק בנושא שרציתי לדון בו. הטענה שלי היא לא שכל מודל מעניין מתמטית הוא בעל משמעות מעשית אלא ספציפית למודל של מעגלים לא יוניפורמיים. אני די מסכים עם הטענה שלך שמכונת טיורינג לא דטרמיניסטית היא "סתם" טריק מתמטי. אפילו בתיאוריה של סיבוכיות כבר לא משתמשים (כמעט) בהגדרה של מכונה לא דטרמיניסטית, אלא בהגדרה השקולה של קיום מוודא (דטרמיניסטי). |
|
|
|
|
|
|
||
|
||||
|
קיום מוודא דטרמיניסטי לא הופך את המודל של NP למופרך פחות, כי ההוכחה צריכה לבוא ממקום כלשהו, וב"עולם האמיתי" אין כזה מקום באופן כללי. כמובן שבמקרים פרטיים יש כזה מקום (נניח, אתה יודע פירוק של מספר כי אתה חישבת אותו מלכתחילה על ידי הגרלת ראשוניים והכפלתם) ואז התיאור של NP מתאים, אבל באופן כללי אין, ומכאן ה"מופרכות". | |
|
|
|
|
|
||
|
||||
|
אוי. חבל שאתה מנסה להתווכח עם דברים שלא כתבתי. כתבתי שמכונת טיורינג לא דטרמיניסטית היא ''סתם'' טריק מתמטי ולא שמוודא דטרמיניסטי אינו כזה. עוד יותר חבל בגלל שמוודא דטרמיניסטי זה דווקא משהו שאני ואתה עושים כל הזמן. כל פעם שאתה קורא ספר או מאמר ו''מבין'' (כלומר בודק) את ההוכחות המופיעות בו, אתה למעשה משמש כמוודא דטרמיניסטי. תרגיש חופשי להגיב למה שכתבתי אבל, ברשותך (או שלא ברשותך), אני לא מתכוון לענות. אני מרגיש שבינתיים סיימתי את תפקידי ההיסטורי בדיון הזה. שלא לדבר על כך שמישהו כבר ביקש ממני לבחור כינוי והמחויבות קצת מלחיצה אותי (לא באמת). אולי אם ממש יבער לי אני אשוב. |
|
|
|
|
|
|
||
|
||||
|
אני לא מנסה להתווכח. אני מנסה להגיע להסכמה דווקא. קיוויתי שברור מההודעה הקודמת שלי שאין לי בעיה עם הרעיון של המוודא אלא עם המקור של ההוכחה, כלומר עם העובדה שהמודל החישובי הכולל של NP דורש גם מקום שממנו ההוכחה תבוא, וכזה מקום באופן כללי אין. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |