מכונת טיורינג, 2: הנקמה (המסובכת)

עד עכשיו ניסיתי לדבר על סיבוכיות של אלגוריתמים, במונחים של “הזמן שלוקח לאלגוריתם לרוץ”. זה מדד די אידיוטי. הרי אלגוריתם זה יצור מופשט לגמרי, להבדיל מתוכנית מחשב - ובטח שלא לוקח זמן שנמדד בשניות כדי “להריץ” אלגוריתם. אם כך, איך ניתן להעריך את כמות הזמן שייקח לאלגוריתם לרוץ?

למרבה המזל, אלגוריתם מורכב ממספר סופי של צעדים בסיסיים. אפשר להניח שכל אחד מהצעדים הללו לוקח פרק זמן קבוע כלשהו - לא חשוב כמה במדוייק - וכל מה שנותר לעשות הוא לחשב כמה פעמים יופעל כל צעד. למשל, הנה אלגוריתם לבדיקת ראשוניות של מספר n:

1. אתחל את i להיות 2.
2. חלק את n ב-i ובדוק האם התקבלה שארית.
   1. אם לא, סיים ופלוט "n אינו ראשוני".
3. הגדל את i ב-1.
4. בדוק האם i שווה ל-n.
   1. אם כן, סיים ופלוט "n ראשוני"
   2. אחרת, חזור ל-2.

צעד האתחול לוקח פרק זמן קבוע כלשהו \( c_1 \) - אבל לעולם לא נחזור אליו בהמשך. צעד החילוק ובדיקת השארית לוקח \( c_2 \) פעמים ובמקרה הגרוע ביותר נחזור עליו \( n-1 \) פעמים. כך גם עבור הגדלת i ובדיקת השוויון ל-n. בסך הכל נקבל שהאלגוריתם לוקח את המספר הבא של צעדים:

\( c_1+(n-1)(c_2+c_3+c_4) \)

כלומר, קבוע ועוד פונקציה שהיא “כמעט” n, כפול עוד קבוע. כל העסק הזה הוא, בסיכומו של דבר, \( O(n) \), וזו גם סיבוכיות האלגוריתם (שימו לב - אני מרמה כאן ומחשב את הסיבוכיות על פי ערכו של n ולא על פי גודל הייצוג שלו). אם כן, לא מעניין אותנו כמה זמן כל צעד ייקח בפועל - מעניין אותנו רק כמה צעדים (מכל סוג שהוא) יהיו לאלגוריתם, פחות או יותר. נקודת המבט הזו היא בסדר גמור לרוב הצרכים המעשיים, אבל כשנכנסים ברצינות לתיאוריה (וזה מה שאני מקווה לעשות כאן) זה לא מספיק. הבעיה היא בכך שאלגוריתמים בכל זאת מחביאים בתוכם דברים מסובכים שעליהם אולי לא חשבנו. למשל, אמרתי ש”חלק את n ב-i ובדוק את השארית” הוא צעד בסיסי. האמנם? לפחות מבחינה נאיבית, כדי לבצע חלוקה של מספר בגודל n, נדרש פרק זמן שהוא פונקציה של n - בערך כמספר הספרות של n. כלומר, הצעד ה”בסיסי” הזה מחביא בתוכו צעדים שאינם בסיסיים ושתלויים בגודל הקלט.

הדרך לפתור את הבעיה היא להגדיר סט של פעולות שהן כן יסודיות - למשל, במחשב, כל פעולה שמתבצעת ב-CPU יכולה להיחשב בסיסית. מכיוון שה-CPU יודע לעבד רק מספרים עד גודל מסויים, עיבוד של n גדול יהיה חייב להתבצע במספר פעולות, בזו אחר זו - ולכן נקבל שהחילוק אכן דורש מספר פעולות CPU. הבעיה כאן היא שהגישה הזו אינה מופשטת מספיק; CPU יכול להיות דבר מאוד מסובך ולא כדאי להיכנס לניתוח המדוייק של איך אלגוריתם שמתורגם לתוכנית מחשב יבוצע בו.

לכן חוזרים אל המודל האלמנטרי ביותר למחשב שאנו מכירים - מכונת טיורינג. מכונת טיורינג מבוססת על “צעדים”, שבכל אחד מהם זזים תא אחד על פני הסרט ועוברים ממצב פנימי אחד לאחר. הרי לנו מדד סיבוכיות זמן מצויין - מספר הצעדים שהמכונה מבצעת. באותה הזדמנות מגיע גם מדד סיבוכיות זיכרון טוב - כמות הסרט שבו השתמשה המכונה (ההגדרה המדוייקת לסיבוכיות זיכרון קצת יותר מחוכמת, אך לא אכנס אליה כעת).

אלא שכאן מגיעה בעיה חדשה. מכונת טיורינג, במודל הפשוט ביותר שלה, היא, אה.. פשוטה. מצד אחד זה טוב, כי קל לנתח אותה במדוייק, אבל מצד שני זה רע, כי קשה מאוד לתאר אלגוריתים באמצעות מכונת טיורינג. לכן מחפשים מודל שקול, שיהיה יותר נוח לתאר באמצעותו אלגוריתמים, אבל זמן הריצה (האסימפטוטי) הן עליו והן במכונת הטיורינג ה”פשוטה” יהיה זהה. לרוע המזל, אם אנחנו דבקים בהשארת זמן הריצה ללא שינוי מהותי, המודלים ה”חזקים יותר” שנקבל גם כן לא יהיו נוחים למדי. צריך לעשות פשרה כלשהי; הפשרה המקובלת במדעי המחשב בימינו היא ההכרזה על כל אלגוריתם שעל מכונת טיורינג רץ על קלט מגודל n מספר צעדים שהוא פולינום ב-n כעל אלגוריתם “יעיל”.

למה פולינומים? ראשית, כי זמן ריצה של n על קלט בגודל n נחשב מצויין. לכן בוודאי שהוא יהיה זמן יעיל - והוא כבר פולינום, פשוט (ממעלה 1). כעת, מעבר ממודל אחד של מכונת טיורינג למודל מורכב יותר עשוי לגרום לזמן הריצה לגדול ולהפוך לפולינום של זמן הריצה המקורי - למשל, לעלות בריבוע. כלומר, אלגוריתם שעל המודל המורכב לוקח רק n צעדים ייקח \( n^2 \) צעדים במודל הבסיסי. לכן הפשרה היא לקבל אל חיקנו את כל הפולינומים.

אם הפולינומים נחשבים “יעילים” (איך לעזאזל \( n^{100} \) יכול להיחשב זמן יעיל?), מה לא יעיל? הדוגמה האלמנטרית היא הפונקציות האקספוננציאליות - \( 2^{n} \), למשל. פונקציות שבהן n אינו “למטה” (בבסיס החזקה) אלא “למעלה” (במעריך החזקה). עד כמה ש-\( n^{100} \) נראה לא יעיל, \( 2^{n} \) עובר אותו מהר יחסית (עבור n=1,000, למשל - ואם המספר הזה נראה לכם גדול תחשבו על אלגוריתם חיפוש שרץ על טקסט באורך מיליוני תווים, ותזכרו שאלגוריתם RSA בימינו עובד עם מספרים בני 1,024 ביטים). יש פונקציות לא יעילות שהן קטנות וגדולות מהאקספוננציאליות, אבל לא נרחיב עליהן את הדיבור יותר מדי. החשיבות היא בכך שכעת תמונת העולם שלנו מחלוקת לשלושה חלקים - יש את הבעיות האלגוריתמיות שכלל אינן כריעות. הבעיות שכן כריעות מסומנות ב-R, אבל כרגע חילקנו אותן שוב - לבעיות שהן כריעות אבל לא ניתנות לפתרון יעיל (כלומר, כל אלגוריתם שפותר אותן אינו יעיל), ובעיות שהן כריעות וניתנות לפתרון יעיל. את אוסף הבעיות הזה מסמנים ב-P (מלשון Polynomial, פולינומי - על שם זמן הריצה), וזו ככל הנראה מחלקת הבעיות החשובה ביותר במדעי המחשב התיאורטיים.

כל זה עסק במדדי זמן. גם למדדי זיכרון יש מחלקה דומה - המחלקה PSPACE (מלשון Polynomial Space). שתי המחלקות הללו - P ו-PSPACE מדברות רק על בעיות הכרעה, כאלו שבהן צריך להגיד “כן” או “לא”. עבור פונקציות יש מחלקות דומות, אך לא נעסוק בהן לעת עתה.

די בבירור, P מוכל ב-PSPACE - הרי מודדים צריכת זיכרון על ידי כמות הסרט שהמכונה משתמשת בה (ופירוש הדבר, גם אם איני מסביר פורמלית איך עושים זאת, בכמות הסרט שהמכונה “עוברת עליו” בשלב כלשהו של ריצתה). כלומר - על כל יחידת זכרון שצורכים בסרט, חייבים להשקיע לפחות יחידת זמן אחת (כדי לנוע אליה), ומכאן שתמיד צורכים פחות זיכרון מאשר זמן - ולכן מה שנפתר בזמן יעיל, בטח שגם ייפתר בזיכרון יעיל. ההפך אינו ידוע - ייתכן שיש בעיות שניתן לפתור בעזרת זיכרון יעיל, אבל לא באמצעות זמן יעיל (ידועות בעיות רבות שקיים להן פתרון בזיכרון יעיל אך לא ידוע פתרון בזמן יעיל) - ולמעשה, רוב “שדה המשחק” שבו עוסקת תורת הסיבוכיות נמצא בדיוק בין P לבין PSPACE - כלומר, רוב המחלקות (לפחות אלו הבסיסיות) שבהן עוסקים מכילות את P ומוכלות ב- (או שוות ל-) PSPACE.

דבר מעניין שכדאי לשים אליו לב ב-PSPACE הוא שכלל לא חייבים לדרוש שמכונה שמשתמשת בכמות סופית של זיכרון תפסיק את ריצה מתישהו. היא יכולה “לזגזג” שוב ושוב בין מצבים ומקומות על הסרט שהיא כבר קראה, וכלל לא לעצור. עם זאת, לכל מכונה כזו ניתן לבנות מכונה שקולה שמחקה את פעולתה, אך מסוגלת לזהות מתי היא נכנסה ל”לולאה אינסופית” שכזו ולכן לעצור. הדרך לעשות זאת היא כדלהלן: מכיוון שכמות הזיכרון שבה משתמשת המכונה המקורית היא חסומה, לוקחים חסם עליה (כמובן, צריך לדעת מה החסם אם רוצים לבנות בפועל מכונה שקולה שכזו - אך גם אם לא יודעים מה החסם, עדיין קיימת מכונה שקולה שכזו). כעת, ניתן לאפיין את החישוב של המכונה בתור סדרה של קונפיגורציות (כבר הזכרתי את המושג בעבר) - תיאורים רגעיים של תוכן הסרט הרלוונטי, המצב הפנימי של המכונה והמיקום של הראש הקורא. מכיוון שמספר המצבים של המכונה סופי, ומכיוון שכמות הסרט שבה משתמשים סופית, יש רק מספר סופי של קונפיגורציות, כך שהמכונה המסמלצת יכולה לשמור בצד מערך שלכל קונפיגורציה היא מסמנת “כבר היינו כאן”. אם מגלים שהיינו באותה קונפיגורציה פעמיים, פירוש הדבר הוא שנכנסנו ללולאה אינסופית - ולכן עוצרים מייד ומחזירים “כישלון”.

מה עשינו כאן, בעצם? פתרנו את בעיית העצירה לכל מכונה ב-PSPACE (וגם במחלקות זיכרון חסום גדולות יותר). בפרט, מחשבים הם תמיד בעלי זיכרון חסום, כך שתמיד ניתן לפתור בעיות עצירה עבור מחשבים ספציפיים. הנה כי כן אנו עוזבים את העולם התיאורטי לחלוטין של תורת החישוביות, ומגיעים לעולם ה”מלוכלך” יותר של הסיבוכיות - אך בכמה מובנים, גם המורכב והמעניין פי כמה.