לא מדויק

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

1) “חבורה מסדר 6″ - קיימות בדיוק שתיים כאלו. האחת היא - החבורה הציקלית עם 6 איברים (באופן כללי, לכל מספר איברים, קיימת חבורה ציקלית אחת ויחידה עם מספר איברים שכזה). אפשר להראות שכל חבורה אבלית חייבת להיות החבורה הזו (על פי משפט קושי יש תת חבורות נורמליות מסדרים 2 ו-3; ואז החבורה כולה היא המכפלה הישרה של שתיהן, ומכיוון ש-2 ו-3 זרים מקבלים חבורה ציקלית). החבורה השנייה, שאינה אבלית, היא . כל חבורה אחרת עם 6 איברים איזומורפית לאחת משתיהן.

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

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

4) “ההוכחה ש-PRIME שייך ל-P” - הכוונה כנראה היא למאמר “PRIMES in P” המפורסם (קובץ PDF), שמתאר את אלגוריתם AKS שבודק באופן דטרמיניסטי ראשוניות של מספר תוך שימוש בזמן פולינומי בגודל הייצוג של המספר.

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

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

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

8) “איך עוצרים לולאה אינסופית” - מן הסתם לא עוצרים, הרי היא אינסופית! ובכל זאת, ברמת התוכנה, רוב שפות התכנות תומכות בהוראה כמו break שיוצאת מלולאה מייד, גם בלי שיתקיים התנאי שאמור לסיים אותה; וברמת המשתמש, ניתן לסגור תוכנות שנכנסו ללולאה אינסופית מבחוץ על ידי פקודת ctrl+c אם התוכנה הופעלה מתוך טרמינל (חלון DOS או טרמינל של לינוקס, למשל), ואחרת - אפשר להשתמש ב-ctrl+alt+delete הישן והטוב (בווינדוס) לבחור את התוכנה התקועה ולהגיד לווינדוס לחסל אותה בכוח (בלינוקס זה קצת יותר פשוט - ctrl+alt+escape ולחיצה על התוכנה עצמה סוגר אותה בדרך כלל).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

בפועל, סיטואציות שכאלה אינן כה מופרכות גם במציאות. דוגמה פרקטית קלאסית היא מערכת ההצפנה RSA. אמנם, כאן זו לא בעיית כן/לא, אבל הרעיון דומה: כוחה של RSA טמון בכך שמי שיצר את המערכת הגריל שני ראשוניים, p,q, כפל אותם, ופרסם בפומבי את המכפלה, n=pq. כעת, הצפנה היא קלה לכולם בהינתן n (ועוד פרמטר נוסף e שאינו רלוונטי לענייננו), אבל פיענוח בהינתן שרק n ידוע לך היא בעיה קשה. קשה כמו מציאת מחט בערימת שחת. לעומת זאת, אם יש לך “רמז” דוגמת הפירוק של n לשני גורמיו (ומציאת פירוק שכזה היא בעצמה בעיה קשה), הרי שאתה יכול לפענח הצפנות בקלות. אם כן, כאן הסיטואציה היא שאתה עצמך יצרת עבורך את הרמז.

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

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

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

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

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

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

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

אבל P=NP לא הייתה שאלה מעניינת אלמלא NP הייתה מעניינת בפני עצמה - והיא מעניינת בפני עצמה מכיוון שקיימות המוני בעיות שידוע עליהן שהן שייכות ל-NP, אבל לא ידוע אם הן שייכות ל-P. אביא כמה דוגמאות בהמשך, כשאדבר על הקבוצה המעניינת ביותר של בעיות מתוך NP - הבעיות ה-”NP-שלמות” - הבעיות הקשות ביותר ששייכות ל-NP, אלו שאם נפתור בצורה יעילה ולו אחת מהן, הוכחנו כי P=NP.

אולם לפני כן, כדאי להכיר את ההגדרה השקולה של NP, ולצלול אל תוך העולם האי-דטרמיניסטי.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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