בספר "מדריך הטרמפיסט לגלקסיה" של דגלאס אדאמס מסופר על מחשב שנבנה בחיפוש אחר התשובה לחיים, ליקום וכל השאר. לרוע המזל, משך החישוב שנדרש למחשב בכדי לפתור את הבעיה הוא שבעה וחצי מיליוני שנים. אף אם נסכים על כך שהבעיה אותה ניסה המחשב לפתור ניתנת לפתרון, נשאלת השאלה האם זה מעשי לחכות פרק זמן שכזה לפתרון.
המאמר הקודם הציג חלוקה של הבעיות האלגוריתמיות לשני סוגים: הניתנות לפתרון ואלו שאינן ניתנות לפתרון. אלא שלאור שאלת זמן החישוב, חלוקה זו אינה בהכרח מספיקה, ויש מקום לביצוע חלוקה נוספת בתוך קבוצת הבעיות הניתנות לפתרון. חלוקה משנית זו תבדיל בין בעיות "קשות" לבעיות "קלות", מבחינת כמות המשאבים הנדרשת לפתרונן.
מהם אותם משאבים? שני המשאבים הבסיסיים הם זמן וזיכרון מחשב (וקיימים גם סוגים אחרים, כגון צריכת אנרגיה). על הנחיצות של הגבלתם אין ויכוח - איננו יכולים לחכות מיליוני שנים לתשובה, ואף איננו יכולים לבנות מחשב בגודלו של העולם כולו (מה שיידרש אם נזדקק לכמויות עצומות של זיכרון). משהחלטנו להתמקד במשאבים של זמן וזיכרון, השאלה המרכזית היא כיצד נמדוד אותם. תוכנות שרצו לפני מספר שנים במשך חודשים ארוכים, רצות כעת בשברירי שנייה בזכות התפתחות הטכנולוגיה. אף שניתן ככל הנראה להציב חסמים על המהירות שאליה תביא אותנו הטכנולוגיה הקיימת, נעדיף למצוא חסמים מופשטים ככל הניתן, שאינם תלויים במכונה הספציפית שעליה ממומש האלגוריתם הפותר את הבעיה. כאן מוכחת פעם נוספת יעילותו של המודל המתמטי המופשט של מחשב שהצגנו במאמר הקודם – מכונת טיורינג.
קל מאוד למדוד זמן ריצה ושימוש בזכרון על גבי מכונת טיורינג: זמן הריצה הוא מספר צעדי החישוב שהמכונה מבצעת (כל צעד חישוב כולל מעבר בין שני מצבים פנימיים של המכונה, כתיבה אפשרית על המקום הנוכחי בסרט והזזה אפשרית של הסרט בצעד אחד). הזכרון שבו השתמשה המכונה הוא כל התאים שהראש עבר על פניהם במהלך ריצתו (אם כי קיימות הגדרות עדינות יותר, שלא ניכנס אליהן כאן). הדרך הפשוטה ביותר להערכת יעילותו של אלגוריתם היא בדיקה של כמות המשאבים המקסימלית שלה יזדקק אלגוריתם זה בריצה על קלט כלשהו. במילים אחרות, כמה משאבים ינצל האלגוריתם במקרה ה"גרוע" ביותר.
כל אלגוריתם שקורא את כל הקלט שהועבר אליו (ורוב האלגוריתמים צריכים לעשות זאת) יבזבז כמות זמן כלשהי רק על קריאת הקלט, וככל שיגדל הקלט כך יגדל פרק זמן זה. לכן, כמות הזמן המקסימלית לה אלגוריתם שכזה יזדקק בריצה על קלט כלשהו היא אינסופית - אנחנו יכולים לגרום לאלגוריתם לבזבז כמה זמן שרק נרצה אם נעביר לו קלט ארוך מספיק. לכן, כדי שהמדד שלנו יהיה בעל ערך כלשהו, עליו להתייחס לגודל הקלט עליו פועל האלגוריתם. לפיכך אנו מודדים את זמן הריצה ואת כמות הזיכרון המנוצלים כפונקציה של אורך הקלט.
לדוגמה, נתבונן באלגוריתם שמקבל סדרה של אפסים ואחדות ואומר האם הספרה "1" מופיעה פעמיים ברצף במהלך הסדרה. כל מה שהאלגוריתם צריך לעשות הוא להתחיל לנוע לאורך הסדרה, לזכור מה ראה בצעד הקודם ולהשוות זאת לצעד הנוכחי. אם יראה "1" פעמיים ברצף, יעצור מייד עם תשובה חיובית. אחרת, יחזיר תשובה שלילית לאחר שיגיע לסוף הקלט.
קיימים קלטים שעליהם האלגוריתם יעצור כמעט מייד: אם הקלט נפתח בזוג "11", האלגוריתם יעצור מייד ואין זה משנה אם אחרי שתי הספרות הפותחות ישנן מיליארדי ספרות נוספות. אולם, אנו מתעניינים במקרה הגרוע ביותר, ומקרה זה יתרחש כאשר אין זוג "1" סמוכים בכל הקלט. במקרה זה ניאלץ לקרוא את הקלט עד סופו כדי להיות בטוחים שלא פספסנו כלום, ופרק הזמן שנבזבז יהיה פרופורציונלי לאורך הקלט: על קלט כפול באורכו, זמן הריצה שלנו יהיה בערך כפול באורכו. זאת מכיוון שעיקר הזמן מתבזבז על תנועה לאורך הקלט, והזמן שלוקח לבצע צעד בודד הוא קבוע. על זמן ריצה שכזה אומרים שהוא לינארי באורך הקלט.
חישוב פשוט? (צילום: MorgueFile)
זמן ריצה לינארי שכזה נחשב זמן ריצה טוב למדי. כדי לקבל המחשה לכך, נשווה אותו לזמן ריצה שהוא פרופורציונלי לריבוע אורך הקלט (זהו זמן ריצה שמאפיין, למשל, אלגוריתמי מיון נאיביים): אם הגדלנו את הקלט פי 10, הרי שזמן ריצת אלגוריתם לינארי על הקלט המוכפל יוכפל פי 10, בעוד שזמן ריצת אלגוריתם ריבועי יוכפל פי 100. ככל שהקלטים הולכים וגדלים, כך היתרון של זמן הריצה הלינארי הולך וגדל. אם כן, על פניו נראה שזמן ריצה לינארי מתאים לתפיסה שלנו של "חישוב יעיל" ואפשר להשליך את שאר זמני הריצה לעזאזל. בפועל, יש בעיות רבות שלא ניתן לפתור בזמן ריצה לינארי (למשל, בעיית מיון כללית לא ניתנת לפתרון בזמן ריצה שכזה), וההפרדה בין זמני ריצה שנחשבים יעילים לכאלו שנחשבים לא יעילים מתבצעת בין שתי מחלקות רחבות יותר של פונקציות – הפולינומיות מול הסופר פולינומיות, שמכונות (בצורה לא לחלוטין מדוייקת) "האקספוננציאליות". מי שכל הדבר הזה מפחיד אותו צריך לזכור רק את ההבחנה הפשוטה הזו: פולינומי – טוב, אקספוננציאלי – רע.
בצורה הפשוטה ביותר ניתן לומר שזמן ריצה הוא פולינומי אם הוא לא גדול יותר מאשר קבוע מספרי כלשהו כפול חזקה של גודל הקלט. זמן ריצה לינארי וזמן ריצה ריבועי שניהם פולינומיים, אך החזקה יכולה להיות גבוהה אף יותר מאשר ריבוע, ופירוש הדבר הוא שגם חישוב שדורש זמן פולינומי יכול לארוך זמן רב. עם זאת, קצב הגידול של משך החישוב עבור זמני ריצה פולינומיים הוא קטן יחסית לעומת קצב הגידול עבור זמני ריצה אקספוננציאליים.
ניתן להמחיש זאת על ידי דוגמה: אלגוריתם פולינומי מסויים רץ על קלט בגודל 10 במשך אלפית שניה, בזמן שעמיתו, האלגוריתם האקספוננציאלי, רץ במשך מאית שניה על אותו קלט. לא הבדל גדול. לעומת זאת, על קלט בגודל 50 האלגוריתם הפולינומי ירוץ במשך חמש אלפיות שניה, בעוד עמיתו האקספוננציאלי ידרוש חמש שניות. הבדל קצת יותר בולט (כאשר תוכנה רצה במשך חמש שניות, ניתן כבר "להרגיש" את הזמן שנדרש לריצה), אך עדיין לא משמעותי. לעומת זאת, אם נגדיל את הקלט עוד קצת, לגודל 100, האלגוריתם הפולינומי ירוץ במשך מאית שניה, בעוד עמיתו האקספוננציאלי ירוץ 30 שנה. אם נגדיל את הקלט לגודל 1000 האלגוריתם הפולינומי ירוץ עשירית שניה, בעוד עמיתו האקספוננציאלי ירוץ במשך פרק זמן שכדי לתארו נזדקק למספר עם עשרות אפסים – פרק זמן גדול בהרבה מגילו של היקום.
אם כן, הפונקציות האקספוננציאליות גדלות הרבה יותר מהר מאלו הפולינומיות, וזה נותן לגיטימציה בסיסית לביצוע ההפרדה דווקא בין שתי הקבוצות הללו. ישנן תכונות נוספות, שלא ניכנס אליהן כאן, שבגללן בוחרים להתייחס לכל הפונקציות הפולינומיות כמייצגות חישוב יעיל.
את אוסף כל הבעיות שניתן לפתור באמצעות מכונת טיורינג בזמן ריצה פולינומי נהוג לסמן באות P, מלשון Polynomial. זהו ה-P שמופיע בשאלת "P=NP", אליה נגיע עוד מעט.
קדחת השחת
בעיות פרקטיות רבות בהן אנו עוסקים נמצאות ב-P: מיון, חיפוש ברשימה, ביצוע פעולות חשבון מורכבות ועוד. לעומתן, קיימות בעיות שניתן להוכיח כי הקושי שלהן הוא אקספוננציאלי, ולא משנה כמה נתאמץ לחפש אחר אלגוריתם יעיל שפותר אותן (למשל, במקרה של בעיית מגדלי האנוי, רק כתיבת הפתרון דורשת זמן אקספוננציאלי במספר הטבעות). נתמקד כעת במחלקה של בעיות שלא ידועה עבורן הוכחה כזו, ולפחות במובן אחד הן בעיות פשוטות, אך לא ידוע אם כולן שייכות ל-P. מחלקה זו נקראת NP.
ישנן שתי דרכים עיקריות לתאר את NP. האחת מתבססת על מושג האי־דטרמיניזם (שנציג במאמר הבא), והדרך השנייה היא לתאר את NP בתור אוסף כל הבעיות, שחיפוש פתרון עבורן עשוי להיות קשה, אך בהינתן מידע נוסף, אימות הפתרון הוא קל. בתור דוגמה נחשוב על בעיית המחט בערימת השחת.
נניח שאנחנו ניצבים אל מול ערימת שחת ענקית, ונשאלים שאלת "כן/לא" פשוטה: האם יש מחט בערימה הזו? כיוון שאין לנו מושג איך מוצאים מחט בערימת שחת, אנחנו משתמשים באלגוריתם נאיבי ביותר לפתרון הבעיה: אנו מרימים אניץ קש אחד, הולכים כמה מטרים הצידה ומניחים אותו שם, חוזרים לערימה, לוקחים עוד אניץ קש וחוזר חלילה. בסופו של דבר נעביר את כל הערימה מצד אחד לצד השני, ותוך כדי התהליך, אם קיימת מחט בתוך הערימה, נבחין בה.
אני עוד אמצא את המחט הזו...
נשמע נורא? נכון. שיטות עבודה "ישירות" שכאלו מכונות "ראש בקיר" (brute force). הן עובדות; אנחנו לא מתמודדים עם בעיה בלתי־פתירה כמו בעיית העצירה. לרוע המזל, הן עובדות לאט, וככל שהקלט גדול יותר, כך הנזק גדול פי כמה.
אבל עכשיו בואו נניח שבעוד אנו בוהים בערימת השחת ומנסים לנחש אם יש בה מחט או אין, בא אלינו מישהו ואומר "בטח שיש מחט בערימה, תראו!", שולח את ידו לתוך הערימה ומייד שולה את המחט. במקרה הזה נוכל להחזיר מייד תשובה חיובית - יש מחט בערימה. מה קרה כאן? ברגע שנתקלנו במישהו שסיפק לנו "הוכחה" לכך שהתשובה לשאלה היא "כן", היה לנו קל לוודא שזו אכן התשובה. שימו לב לכך שאם אין בערימה מחט, אין לנו דרך קלה לוודא זאת. כלומר, אם הבעיה פתירה, קיים "רמז" שעוזר לנו לראות זאת בקלות (לרוב הרמז הוא פשוט אחד הפתרונות), אך אין לנו בהכרח דרך קלה לוודא שלא קיים פתרון כלל.
נעבור לדוגמה יותר מציאותית – פירוק לגורמים. נביט במספר 50: הוא זוגי, כלומר ניתן לחלק אותו ב-2 ולקבל 25. את 25 אפשר לחלק ב-5 ולקבל 5. לעומת זאת את 5 אי אפשר לחלק יותר באף מספר ששונה מ-5 ומ-1, כלומר, הוא מספר ראשוני. גם 2 הוא ראשוני. לכן גילינו שאפשר לכתוב את 50 בתור המכפלה 2*5*5. כל המספרים שמשתתפים במכפלה הזו הם ראשוניים, ולכן אי אפשר להרחיב את המכפלה עוד יותר. המכפלה הזו היא הפירוק לגורמים ראשוניים של 50. כידוע, לכל מספר טבעי יש פירוק יחיד לגורמים ראשוניים.
אם נתון לנו מספר, כמה קשה למצוא את הגורמים הראשוניים שלו? לכאורה מדובר במלאכה פשוטה למדי: עוברים על כל המספרים הראשוניים הקטנים ממנו ומנסים לחלק אותו בהם. אם מצליחים לחלק, מוסיפים את המחלק לרשימת הגורמים הראשוניים וממשיכים בחיפוש. השיטה הזו היא דוגמה נוספת לשיטת "ראש בקיר", וגם כאן מחירה (במונחי זמן ריצה) הוא עצום, גם אם הדבר לא ברור ממבט ראשון. הסיבה לכך היא שקל יחסית לייצג במחשב מספרים גדולים מאוד, נניח בני 400 ספרות (לשם השוואה, מספר השניות שמוערך כי חלפו מאז תחילת היקום הוא בן 18 ספרות); אבל אין שום סיכוי לעבור, בפרק זמן סביר, ולו על שבריר מכמות המספרים שקטנים ממספר כה עצום.
לעומת זאת, גם כאשר עוסקים במספרים בני 400 ספרות, ניתן לכפול אותם בזמן סביר. בשל כך, אם מישהו טוען שמצא פירוק לגורמים של מספר גדול, קל לבדוק זאת: פשוט כופלים את כל המספרים בפירוק ובודקים האם התוצאה שהתקבלה היא המספר שניסינו לפרק. לכן גם בעיית הפירוק לגורמים שייכת לאוסף הבעיות שלא מכירים דרך יעילה לפתור אך קל לוודא שפתרון נתון עבורן הוא נכון, כלומר ל-NP.
לבעיה התמימה הזו יש חשיבות מעשית רבה. שיטת ההצפנה RSA, שנמצאת בשימוש נרחב, מתבססת על ההנחה שמציאת פירוק לגורמים היא קשה. כל עוד לא ידוע אלגוריתם יעיל לפירוק לגורמים, RSA היא שיטה בטוחה יחסית (אם כי הוכחה שלא קיים אלגוריתם שכזה עדיין לא תבטיח לגמרי את בטיחותה). אם יתגלה אלגוריתם שכזה (ואולי כבר התגלה, וקיומו נשמר בסוד?) ניתן יהיה לפצח בקלות כל הצפנה באמצעות RSA. כלומר, בעית הפירוק לגורמים היא דוגמה לסיטואציה שבה ניתן להפיק תועלת דווקא מכך שבעיה מסויימת נחשבת קשה!
הולכים אל הלא נודע
כל הדיון עד כה היה מבוא לשאלה, שהיא אחת השאלות הפתוחות המרכזיות כיום במדעי המחשב התיאורטיים, ואפילו זכתה להיכלל בין "7 בעיות המילניום" של מכון קליי למתמטיקה: שאלת P=NP.
השוויון שמופיע בשם השאלה הוא שוויון בין אוספי הבעיות שב-P וב-NP (ולכן התשובה אינה "כן, אם N=1 או P=0"). אנחנו יודעים שכל בעיה ב-P שייכת ל-NP (אם קל לפתור משהו, קל לבדוק אם הוא ניתן לפתרון או לא), ולכן השאלה הקשה היא בכיוון ההפוך – האם כל בעיה ששייכת ל-NP גם שייכת ל-P? האם מספיק לדעת שקל לבדוק את חוקיותו של פתרון לבעיה, כדי שמובטח יהיה שניתן לפתור אותה בקלות?
עד היום טרם נמצא פתרון לשאלה הזו, וחלק משיטות ההוכחה המקובלות במדעי המחשב הוכחו כלא יעילות לחיפוש הפתרון. פרס של מיליון דולר ויוקרה גדולה בתחום מדעי המחשב מובטחים למי שיפתור אותה, אך טרם נמצא פותר שכזה. לכן ניתן להניח במידה לא מבוטלת של סבירות שזוהי בעיה קשה, ופתרונה (אם ניתן לפתור אותה) דורש טכניקות מתמטיות שכנראה עוד לא נמצאו. הדעה הרווחת בקרב מדעני המחשב היא שהשוויון אינו נכון.
חשוב להדגיש שמדובר בשוויון בין אוספי הבעיות – כלומר, פירוש השוויון הוא כי כל בעיה שניתן לוודא את פתרונה ביעילות, ניתנת לפיתרון באופן יעיל. גם אם P שונה מ-NP, אין פירוש הדבר כי כל בעיה ב-NP לא ניתנת לפתרון יעיל; ישנן דוגמאות של בעיות שהיו ב-NP ולא היה ברור אם הן ב-P, ולבסוף התגלה שהן ב-P. הדוגמה הידועה ביותר היא כנראה זו של בדיקת ראשוניות: במשך שנים רבות לא היה ידוע אם ניתן לבדוק בזמן סביר האם מספר נתון הוא ראשוני (כלומר, לא היה ידוע אם הבעיה ב-P), אך הייתה ידועה הוכחה כי קיימת דרך לוודא בזמן סביר, בהינתן מידע מסויים, שמספר הוא ראשוני – כלומר, היה ידוע כי הבעיה ב-NP (ניתן גם לוודא בקלות בזמן סביר שמספר אינו ראשוני אם מציגים מספר שבו הוא מתחלק; בעיות שניתן לוודא בקלות את אי־נכונותן שייכות למחלקת co-NP). האלגוריתם המקובל לביצוע בדיקת ראשוניות היה הסתברותי – הוא עבד כמעט תמיד, אך הייתה קיימת הסתברות נמוכה מאוד שהוא יטעה, ויגיד על מספר פריק שהוא ראשוני. רק בשנת 2002 התגלה אלגוריתם שעובד בזמן פולינומי ואינו הסתברותי. בפועל, זמן הריצה שלו גדול יותר מזה של האלגוריתם ההסתברותי, ולכן למרות הגילוי ממשיכים להשתמש באלגוריתם ההסתברותי (קיימים אלגוריתמים יעילים נוספים, שחלקם מתבסס על השערות בתורת המספרים שטרם הוכחה נכונותן).
עם זאת, יש קבוצה לא קטנה של בעיות שהן במובן מסויים הבעיות הקשות ביותר ב-NP. אם יתגלה ש-P אינה שווה ל-NP, זה יבטיח שאף אחת מאותן בעיות אינה ב-P, ואילו אם יוכיחו ולו על בעיה אחת מתוכן שהיא ב-P, הדבר יוכיח כי P=NP. לבעיות החשובות הללו קוראים בעיות NP-שלמות.
אלגוריתים להכנת תה
בדיחה ידועה מספרת על פיזיקאי ומתמטיקאי המתבקשים להכין כוס תה. הפיזיקאי נוטל קומקום ריק, ממלא אותו מים, ממתין עד שהמים ירתחו ואחר כך מוזג חלק מהם לכוס. כשמבקשים מהמתמטיקאי להכין כוס תה נוספת הוא נוטל את הקומקום, שעדיין מלא במים רותחים, מרוקן את תוכנו לכיור ואומר "עכשיו חזרנו לבעיה שאותה אנחנו כבר יודעים לפתור".
בבדיחה המטופשת הזו יש גרעין לא קטן של אמת: דרכי העבודה של המתמטיקאי לעתים קרובות מתבססות על מעבר מבעיה אחת, קשה, לבעיה אחרת, שאת פתרונה אנו כבר מכירים. הדרך בה הוכח המשפט האחרון של פרמה היא כזו: השאלה האם משפט פרמה נכון צומצמה לשאלה האם השערה ידועה אחרת במתמטיקה, שנקראה "השערת טניאמה שימורה", נכונה. משהוכחה השערת טניאמה שימורה, נבעה גם נכונותו של משפט פרמה. כמובן שאין צורך להרחיק עד למשפט שנדרשו למעלה משלוש מאות שנים להוכיח כדי להביא דוגמה לצמצום שכזה – גם סטודנט שנה א' למתמטיקה ייתקל במקרים רבים שבהם דרך הפעולה הזו, המכונה "רדוקציה", תתגלה כשימושית. מכיוון שמדעי המחשב קשורים למתמטיקה בקשר הדוק, אין זה פלא שגם בהם דרך העבודה הזו יעילה.
ישנם מספר סוגים שונים של רדוקציות, אך בהקשר של שאלת P=NP, המעניינת ביותר היא רדוקציה שבה לוקחים מקרה של בעיה ב' והופכים אותו למקרה של בעיה א', כאשר הטרנספורמציה הזו מתבצעת בזמן פולינומי. הדבר מבטיח שאם אנו יודעים לפתור את בעיה א' בזמן פולינומי, הרי שגילינו איך לפתור את ב' בזמן פולינומי – פשוט נמיר אותו לא' ואז נפתור את א' (סכום הזמנים של שתי פעולות פולינומיות – ההסבה והפתרון – גם הוא פולינומי).
למשל, אם אנו רוצים לדעת האם מספר הוא ראשוני, ואנו מכירים אלגוריתם יעיל שמחזיר את הפירוק שלו לגורמים, פשוט נפעיל את האלגוריתם ונספור אם קיבלנו יותר מגורם יחיד. כמובן שהדוגמה הספציפית הזו לא מציאותית במיוחד – כבר קיים אלגוריתם יעיל (פחות או יותר) לבדיקת ראשוניות אבל טרם נמצא אלגוריתם יעיל לפירוק לגורמים – ובכל זאת היא מדגימה את משמעות הרדוקציה.
הבעיות ה-NP-שלמות הן בעיות ששייכות ל-NP ומאופיינות בתכונה המעניינת לפיה כל בעיה אחרת ב-NP ניתנת לרדוקציה אליהן. כלומר, אם פתרנו בעיה שהיא NP-שלמה בצורה יעילה, נוכל לפתור כל בעיה ב-NP בצורה יעילה על ידי ביצוע רדוקציה אל הבעיה ה-NP-שלמה שפתרנו. בפרט, הדבר יוכיח מייד כי P=NP. לכן זוכות הבעיות ה-NP שלמות ל"הדרת כבוד" מיוחדת – מצד אחד, אם P=NP, ייתכן מאוד שהדרך להוכיח זאת תעבור דרך פתרון יעיל של אחת מהן. מצד שני, אם P אינו שווה ל-NP, פירוש הדבר הוא שאין סיכוי שאף בעיה שזכתה לתואר "NP-שלמה" ניתנת לפתרון יעיל (ולכן ניתן להסתמך על אי־היכולת לפתור אותה באפליקציות של הצפנה, למשל).
שאלה מעניינת אחת שיכולה להתעורר היא איך מראים בכלל שבעיה היא NP-שלמה. לכאורה זה נראה מסובך – הטענה לפיה כל בעיה ב-NP ניתנת לרדוקציה לבעיה NP-שלמה היא טענה גורפת למדי. בשנת 1971 פרסם סטיבן קוק מאמר שבו הוכיח שבעיה בשם SAT היא NP-שלמה. באופן בלתי־תלוי הוכח המשפט גם בידי לאונרד לוין (ראוי לציין שהמושג של "NP-שלמות" נטבע רק אחרי פרסום המאמר). לא ניכנס כאן להגדרה המדוייקת של בעיית SAT, שמתבססת על תחשיב הפסוקים בלוגיקה והיא טכנית למדי. הרעיון הבסיסי בהוכחה של קוק היה לתרגם חישובים של מכונות טיורינג לפסוקים לוגיים, כך שלפסוק יהיה ערך אמת (או יותר במדוייק: תהיה קיימת השמה שמספקת אותו) אך ורק אם יש פתרון לבעיה שמבקשים לעשות רדוקציה ממנה ל-SAT.
ההוכחה של קוק ולוין היא מסובכת יחסית, אך לאחר שהוכח ש-SAT היא NP-שלמה, נפתחה הדרך להוכיח על אלפי בעיות אחרות שגם הן NP-שלמות, מכיוון שאם יש לנו בעיה שידוע שהיא NP-שלמה, והצלחנו לבצע ממנה רדוקציה לבעיה אחרת, הרי שגם הבעיה האחרת היא NP-שלמה. כבר בשנת 1973 פרסם ריצ'ארד קארפ מאמר ובו הציג 23 בעיות NP-שלמות, וכיום ידועות אלפי בעיות שכאלו.
טרם הסברנו מדוע המחלקה NP נקראת כך. ה-P שבשמה בא מהמילה "פולינומי", בדומה למחלקה P, אולם מה ה-N מייצג? לשם כך נציג דרך אחרת לחשוב על הבעיות שב-NP על ידי הכנסה למשחק של מכונות טיורינג מסוג חדש – מכונות אי־דטרמיניסטיות. על כך – במאמר הבא.
|
קישורים
המאמר הקודם - "מה לא יכול המחשב לעשות", מאת גדי אלכסנדרוביץ'
|
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש