 |
זה לא בהכרח נכון, כי מספר הצעדים כן תלוי במעבד - יש מעבדים שמממשים בתור פרימיטיבים פקודות שבמעבדים אחרים היו לוקחות כמה פקודות מכונה, וכדאי גם לזכור שבימינו יש מחשבים עם מספר מעבדים שרצים בו זמנית. לכן לשאלות של זמן ריצה יכול להיות עניין - לא עניין תיאורטי, חס ושלום, אבל עניין. כדאי לשים לב שלא מדובר כאן על הבדלים מסדרי הגודל שבהם עוסקת תורת הסיבוכיות (למשל, ההבדל בין P ו-NP), אבל זו אכן אחת הסיבות שבגללה תורת הסיבוכיות מגדירה "חישוב יעיל" בתור P למרות מהומת האלוהים שיש בפנים - זה מבטיח לנו אי תלות גדולה יחסית במודל. ובכל זאת, מתחת לכסות ה"תיאורטית" הזו רוחשים חיים "אמפיריים".
הנה דוגמה למשהו שתורת הסיבוכיות בכלל לא רלוונטית אליו: בעיית השחמט. יש משפט של צרמלו שאומר שכל משחק דמוי-שחמט (לא ניכנס למה זה - העיקר ששחמט הוא כזה) מקיים אחת משלוש אפשרויות: או שללבן יש דרך להבטיח ניצחון בכל משחק, בלי תלות במה עושה השחור; או שלשחור יש דרך כזו, או שלכל אחד מהשחקנים יש דרך להבטיח תיקו.
אם נדע ולו על אחת מהדרכים הללו, המשחק יאבד הרבה מהטעם שבו, ובפרט אם נגלה שללבן, למשל, יש דרך להבטיח תמיד ניצחון. באופן תיאורטי, לא קשה לבדוק את זה - פשוט עוברים על "עץ המשחק" (תיאור כל הצעדים האפשריים במשחק) וסורקים אותו עד סופו. מכיוון שגודל עץ המשחק הוא מספר קבוע, ואילו תורת הסיבוכיות מתעניינת בקצב גדילה, הבעייה "לא מעניינת" מבחינתה - אבל זו הרי בכל זאת בעיה מעניינת, והתשובה לה תלוייה בגורמים "מעשיים" בלבד - המימוש היעיל של החיפוש, ואולי גם היוריסטיקות שיסייעו במציאת הפתרון וצמצום מרחב החיפוש.
באשר לקריפטוגרפיה - ייתכן מאוד שאתה צודק וזו בעיה "מתמטית", אבל לא ברורה לי ההפרדה החדה שעושים בינה ובין בעיה פיזיקלית, מבחינת ה"אמפיריות" של הפתרונות.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש