למה גם מה שפתיר לא פתיר (זה מסובך)

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

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

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

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

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

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

כדי לעשות את החיים קלים עוד יותר (מכיוון ש-\( f \) הזו היא בדרך כלל קשה לחישוב) לא מתעמקים בשאלה מה ערכה המדוייק של הפונקציה, אלא רק כמה מהר היא גדלה. הסימון הנפוץ ביותר בהקשר זה הוא “או גדולה” - אומרים ש-\( f(n)=O(g(n)) \) אם קצב הגידול של \( f \) לא גדול יותר מזה של \( g \). למי שמתעניין בפורמליזם המדוייק: זה אומר ש-\( \lim_{n\to\infty}\frac{f(n)}{g(n)}<\infty \).

כדי לתת מושג כללי על מה מדובר: אלגוריתם שהסיבוכיות שלו היא \( O(n) \) נקרא “לינארי” - זה אלגוריתם מהסוג שבו הכפלת הקלט פי 2 מכפילה את זמן הריצה פי 2 (מכאן ואילך אדבר רק על המשאב הפופולרי יותר של זמן הריצה; על זיכרון אדבר בנפרד). זה פחות או יותר הדבר ה”הוגן” שהיינו מצפים שיקרה. אלגוריתם עם סיבוכיות \( O(n^4) \) הוא מסוג הפי-16 שהזכרתי קודם - כבר גרוע למדי. הנה מספר דוגמאות לבעיות ולסיבוכיות שלהן:

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

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

בדיקת ראשוניות: כאן העניינים מתחילים להסתבך. נראה טבעי לומר שבהינתן \( n \) שרוצים לבדוק את ראשוניותו, הסיבוכיות צריכה להימדד כפונקציה של \( n \), ולכן האלגוריתם הנאיבי לבדיקת ראשוניות (שסיבוכיותו היא \( \sqrt{n} \) הוא אחלה של דבר. אלא שלא כך המצב. גודל הייצוג של מספר בגודל \( n \) (מספר הספרות שלו) הוא \( k=\log n \) (למה?) ולכן, אם מודדים סיבוכיות באמצעות גודל הייצוג, סיבוכיות האלגוריתם הנאיבי היא \( 2^{n/2} \) (אני מניח שכל הלוגריתמים הם על בסיס 2, הנחה מקובלת בתורת הסיבוכיות). לאלגוריתם עם סיבוכיות כזו קוראים אקספוננציאלי והוא נחשב גרוע פי כמה וכמה מכל האלגוריתמים שראינו עד כה. נסו קצת לשחק עם הפונקציה הזו בהשוואה לאחרות ותראו למה.

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

במשך זמן רב לא היה ידוע אלגוריתם שאינו גרוע בערך כמו אלגוריתם אקספוננציאלי עבור בדיקת ראשוניות; היו ידועים אלגוריתמים יעילים לא דטרמיניסטיים, שהותירו סיכוי אפסי (אך לא אפס) לטעות, אולם אלגוריתם דטרמיניסטי יעיל לא היה ידוע עד לשנת 2002, כאשר פורסם אלגוריתם AKS הדטרמיניסטי. הסיבוכיות שלו שופרה מאז הפרסום המקורי וכעת עומדת על \( O(n^{7.5)} \) (כאן \( n \) הוא גודל הייצוג). על פניו, זה מספר מחפיר; האלגוריתמים הלא דטרמיניסטיים עדיין מהירים בהרבה ובפועל משתמשים בהם. אז למה האלגוריתם הזה עורר התלהבות גדולה ונחשב לאחת מהתוצאות החשובות בעשור האחרון? כי פרסומו העביר את בעיית הראשוניות מדרגה, מאוסף הבעיות שנחשבות “בלתי פתירות” מבחינת סיבוכיות, לבעיות שנחשבות “פתירות”, ואפילו “יעילות”, מבחינתה של תורת הסיבוכיות. למה מבוצעת כזו אבחנה מוזרה? איך אלגוריתם עם זמן ריצה גרוע כל כך יכול להיחשב “יעיל”? אנסה לספק לכך הסבר בפעם הבאה.