בתשובה לגדי אלכסנדרוביץ', 07/01/07 20:08
 |
|
 |
||
|
||||
 |
אני מכיר את המודל הזה ומסכים עם מה שאתה אומר ומצטט עליו. הוא מסובך מדי. אם רוצים גישה ישירה, צריך כתובות, ואם צריך כתובות, אז צריך מספר אינסופי של ערכים לכל תא בסרט, ואם יש מספר אינסופי כזה של ערכים אז פונקצית צעדים פשוטה לא מספיקה, צריך אריתמטיקה, ואתה מוצא את עצמך עם מודל שבינו לבין מודל תיאורטי פשוט ומופשט אין הרבה. התאכזבתי ושאלתי את עצמי "מה, אין מודל _פשוט_ ששקול לו מבחינת הסיבוכיות?" |  |
 |
 |
|
|
|
||
|
||||
|
אוקיי, אבל אני לא חושב שזה מאכזב עד כדי כך. במכונת טיורינג משתמשים כדי למצוא את ההבדלים בין דברים שב-P ובין דברים שב-NP, למשל, לא כדי לראות איך אופטימיזציות יכולות לאפשר לנו לחשב את RSA יותר מהר. ניתוח סיבוכיות של אלגוריתמים שניתנים לפתרון יעיל ממילא מבוסס לרוב על בחירה של פעולה מסויימת בתור "הפעולה הבסיסית" שאותה סופרים, לא על ספירת הצעדים שמכונת טיורינג עושה. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |