בעיות מפורסמות במדעי המחשב

האם N=NP או איך לארוז תרמיל ולהרוויח מליון דולר?

הכנה: שמוליק שוורץ, מכון ויצמן למדע

ניתן להשתמש בחומרים לצורך הוראת הנושא לתלמידי תיכון.

לא ניתן לעשות בחומר כל שימוש מסחרי ללא רשות בכתב מראש מיוצרי החומרים.

 

תיאור הבעיה

הבעיה המתוארת בפרק זה עוסקת במיליון דולר המונחים על השולחן במכון המתמטי "קליי".

Clay Mathematics Institute of Cambridge, Massachusetts (CMI)

זוהי אחת מ-  7 בעיות בלתי פתירות שהקהילה המתמטית שמה לעצמה מטרה לפתור אותן בשנים הקרובות.

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

יתכן ואתם תוהים מדוע דווקא אתם תצליחו לפתור את הבעיה, אם היא מספיק קשה כדי להציע עליה מליון דולר, התשובה נמצאת בקטע הלקוח מהסרט "סיפורו של ווייל הנטינג" (במקור השם הוא good will hunting וניתן למצוא את הטקסט כאן).

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

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

 

לפני שנגדיר את הבעיה, נציג שאלה שתעזור לנו להבין במה מדובר.

 

שאלת אריזת התרמילים לטיול השנתי (bin packing) :

נתונים N בקבוקי מים בעלי קיבולות שונות הקטנות מ- 10 ליטר.

ברשותי מספר לא מוגבל של תרמילים המסוגלים להחזיק משקל עד 10 ק"ג (כלומר 10 ליטר).

מהו המספר המינימאלי של תרמילים הדרוש לאריזת N הבקבוקים הללו?
(אסור להעביר מים מבקבוק לבקבוק)

 

תיאור גרפי :

 

תיבת טקסט: תרמיל המסוגל לשאת 10 ק"ג כלומר 10 ליטר מים
 

 

 

 


בדוגמא שלפנינו (1,5,4,1,9) נדרשים שני תרמילים.

 

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

 

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

השאלה היא כמה זמן זה ייקח? או במילים אחרות מהי הסיבוכיות. 

הסיבוכיות במקרה זה נמדדת במונחים שדורשים הסבר. נכיר תחילה את המונחים:

1. סיבוכיות ברמה P – סיבוכיות זו משמעותה שזמן הפיתרון הינו פולינומיאלי, כלומר הסיבוכיות היא מסדר גודל של O(nk). זוהי סיבוכיות זמן סבירה לפתרון בעיות וישנו מספר רב של בעיות השייכות לקבוצה זו, למשל סוגי המיון השונים הנלמדים בשיעורי המחשב. (האות P מייצגת את המילה Polynomial).

2. סיבוכיות ברמה NP – סיבוכיות זו משמעותה שזמן הפיתרון אינו פולינומיאלי כלומר הסיבוכיות גדולה מ O(nk) אבל אם יוצע פיתרון ניתן להכריע האם הוא נכון או לא בזמן פולינומיאלי.
למשל בבעיית הבקבוקים, בהינתן סידור שנטען לגביו שהוא מסדר את הבקבוקים ב
K  תרמילים, ניתן לבדוק בזמן פולינומיאלי (במקרה זה O(n1) ) האם הטענה נכונה.
האות
N  שבסיבוכיות NP מיצגת מושג קצת מורכב יותר, המונח הוא : Non-Deterministic  המשמעות היא שאם יש לנו מחשב שיכול להריץ את הבדיקות לכל ה K ים האפשריים במקביל, אז היינו יכולים למצוא את הפיתרון בזמן פולינומיאלי. הבעיה היא שאין מחשב כזה... אבל תיאורטית ניתן לדון בכך.
ניתן להגדיר הגדרה שקולה בעזרת מכונות טיורינג לא דטרמיניסטית. (ראו גם כאן)

 

באופן גרפי ניתן לסכם זאת כך : 

 

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

 

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

 

לשאלה שנציג שני חלקים:

א. בהינתן גרף, האם קיים מסלול בגרף אשר מבקר בכל קשת בדיוק פעם אחת (מסלול אוילר)?

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

 

לגרף הימני קיים מסלול המילטון אך לא מסלול אוילר.

 

לגרף השמאלי קיים מסלול אוילר אך לא מסלול המילטון.

(A-B-C-D)

 

(D-B-C-B-A-B)

 

 

שאלה זו מוכרת גם כבעיית הגשרים של קניגסבורג .

התמונה לקוחה מהאתר http://www2.eitan.ac.il/ds/more/np.asp

(תמצאו שם הרחבה על מסלול אוילר והסבר קצר נוסף למחלקות ה- NP).

 

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

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

 

הגדרת הבעיה הכללית:

השאלות שהוצגו כאן מייצגות את הבעיה הכללית יותר, והיא בעיית מליון הדולר. הבעיה עוסקת בקשר בין שתי קבוצות, קבוצה אחת נקראת קבוצת  P והיא מכילה את כל השאלות שפתרונן הוא בסיבוכיות פולינומיאלית, הקבוצה שנייה נקראת NP והיא מכילה את כל הבעיות שלא ידוע כיצד לפתור אותן בסיבוכיות פולינומיאלית למשל בעית התרמילים (bin packing) אבל ידוע שאם היה לנו מחשב שיכול להריץ את הבדיקות לכל ה K-ים האפשריים במקביל, אז היינו יכולים למצוא את הפיתרון בזמן פולינומיאלי.
שתי הקבוצות הללו נראות שונות מהותית זו מזו אבל אף אחד לא הצליח להוכיח שהן באמת שונות. אף אחד גם לא הצליח להוכיח שהן דומות כך שבעצם הקשר ביניהן לא ברור.

אם תצליחו להוכיח ש P=NP (למשל להוכיח ששאלת התרמילים שייכת ל P), או ש P≠NP (למשל להוכיח שאין אפשרות לפתור את בעית התרמילים בזמן פולינומיאלי, ושימו לב – זה שעד עכשיו לא הצליחו אינה הוכחה!!)
לא רק שתקבלו את סכום הכסף העגול שהוזכר, סביר להניח שתקבלו גם דוקטורט כבונוס.

 

כדי להקל עליכם בדרככם עליכם להכיר תת קבוצה חשובה בתוך קבוצת ה NP, תת קבוצה זו היא בעצם קבוצת הבעיות הקשות ביותר שנמצאות בתוך NP. הבעיות בתת קבוצה זו נקראות  NP-שלמות (NP-Complete).  

קבוצת הבעיות NP-שלמות מכילה מספר רב של בעיות הדומות לשאלת האריזה בתרמילים ולמסלול המילטון.

 

גרפית מדובר כרגע ב:

 

ואולי אתם תוכיחו ש:

 

המונח הוגדר בנפרד על ידי  Cook ו Levin באמצע שנות ה 70 של המאה הקודמת. קוק הגדיר בעיה האופינית לקבוצה  NP- שלמות אשר אם נפתור אותה בזמן פולינומיאלי אז נוכל בעזרת אלגוריתם שסיבוכיותו היא לכל היותר פולינומיאלית לפתור כל בעיה אחרת ב NP.

נסכם : אם תמצאו פיתרון פולינומיאלי למציאת המספר המינימלי של תרמילים אריזה או למציאת מסלול המילטון או לכל בעיה אחרת ב NP-Complete הוכחתם ש P=NP.

 

אבל מדוע מציאת אלגוריתם זה שווה מליון דולר?

 

אלגוריתם כזה אינו בעיה תיאורטית בלבד, הוא יפתור בעיות אמיתיות בניהול חומרה, בתעשיית האלקטרוניקה, בהצפנה ובתחומים נוספים, העובדה שקיים מגוון של בעיות השקולות זו לזו תגרום לסדרת פתרונות שתתפשט כמו אבני דומינו ותביא למהפכה ממש ביכולת החישוב. כדי להבין את עוצמת המהפכה – שימו לב מה המשמעות של פתרון ממצה למקרה של n=20, עלינו לחשב !20 כלומר : 20*19*18*......2*1.

התשובה היא : 2432902008176640000, מה משמעותו של מספר תמים זה? נניח שהמחשב שלכם מסוגל לבצע 1,000,000,000 פעולות בשנייה כלומר ידרשו למחשב בודד כ  2,432,902,008 שניות לבצע מספר כזה של פעולות.

בשעה יש 3600 שניות כלומר ידרשו לו כ 675806 שעות, שהן כ 28158 ימים שהן כ 77 שנים. (טבלה מסכמת תוכלו למצוא בספר "אלגוריתמיקה – יסודות מדעי המחשב" מאת דוד הראל, האוניברסיטה הפתוחה בפרק הדן בבעיות אלו.)

 

פתרון הבעיה (או ניסיונות לפתרון)

אם היה לי פתרון לבעיה אז ברור שלא הייתי כותב אותו כאן לפני שהייתי מקבל את מיליון הדולר.

אבל לפניכם ניתוח שיקרב אתכם לצורת החשיבה שתוביל לפיתרון (אולי)

בעיית התרמילים בניסוח רשמי :

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

 

סיבוכיות הפיתרון בשיטת בדיקת כל האפשרויות אינה פולינומיאלית.

בניסוח הרשמי גודל תיבות האריזה הוא 1 אנו נישאר עם התרמילים בקיבולת של 10 מטעמי נוחות, הניתוח שקול לחלוטין. נתחיל בפתרון ממצה, לפניכם חלק מהסידורים האפשריים של בעיית הבקבוקים שהוצגה  (1,5,4,1,9):

 

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

 

שימו לב – אנחנו אמורים לבדוק את כל הסידורים האפשריים...

אפשר לראות שקיימת סדרה של פתרונות שגויים ושיש יותר מסידור אחד שמקיים את התנאי.

 

 

תרגיל:

נתונים בקבוקים בגדלים : 3,6,2,1,5,7,2,4,1,9.

נסו לבדוק מה המספר המינימלי של תרמילים הנדרש,

חישבו כיצד להוכיח זאת.

 

למעשה, לא ביקשו מאיתנו לפתור, אלא רק לבנות אלגוריתם.

המחשב יעשה את העבודה בשבילנו!!!

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

 

לפניכם הצעה לאלגוריתם פתרון:

עבור כל בקבוק בצע :  "אם יש מקום בתרמיל פתוח – תוסיף, אם אין אז תפתח תרמיל חדש".

אם נקרא את הנתונים מימין לשמאל, אזי לפי אלגוריתם זה יתבצעו הפעולות הבאות:

9 – אין לו מקום באף תרמיל קודם (כי אין אף תרמיל פתוח)  לכן נפתח תרמיל חדש.              

1 – יש לו מקום בתרמיל של ה 9, נוסיף אותו.

4 – אין לו מקום באף תרמיל קודם לכן נפתח תרמיל חדש.

2 – יש לו מקום בתרמיל של ה 4, נוסיף אותו.

7 – אין לו מקום באף תרמיל קודם לכן נפתח תרמיל חדש.

5 – אין לו מקום באף תרמיל קודם לכן נפתח תרמיל חדש.

1 – יש לו מקום בתרמיל של ה 4 וה 2, נוסיף אותו.

2 – יש לו מקום בתרמיל של ה 4, ה 2 וה 1, נוסיף אותו.

6 – אין לו מקום באף באף תרמיל קודם לכן נפתח תרמיל חדש.

3 – יש לו מקום בתרמיל של ה 7, נוסיף אותו.

אין יותר בקבוקים - סיימנו.

 

אלגוריתם זה נקרא גם First Fit או בקיצור FF.

שמו מתמצת את מהותו – מציבים את הבקבוק הבא בתור במקום הפנוי הראשון האפשרי לו. אולם האם אלגוריתם זה נותן לנו את התשובה לשאלת מינימום התרמילים?
קל לראות שנדרשים רק 4 תרמילים ולא חמישה כדי לארוז את הבקבוקים, אולם האלגוריתם לא מצא זאת.

שימו לב שיש כאן תלות בסדר ה"הגעה" של הנתונים.

 

תרגיל :

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

נמיין את הנתונים, כלומר הסדר מימין לשמאל הוא מגדול לקטן והוא : 1,1,2,2,3,4,5,6,7,9. האלגוריתם מצליח, ידרוש 4 תרמילים בלבד!! אולם אלגוריתם זה לא ימצא תמיד את הסידור המינימלי. למשל כאשר הנתונים הם : 1,2,2,2,3,4,5,6,6,9 האלגוריתם יצור את הסידור הבא :   (1+9)(4+6)(3+6)(2+2+5)(2)

ולא את הסידור המינימלי (1+9)(4+6)(2+2+6)(2+3+5)

 

תרגיל :

תאר כיצד יפעל האלגוריתם הממצה לבדיקת המספר המינימלי של תרמילים הנחוץ לסדרת הבקבוקים 3,6,2,1,5,7,2,4,1,9?

( הסידור הוא - (1,9) (3,7) (4,6) (1,2,2,5) )

 

תרגיל נוסף :

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

 

על  Cook (בהרחבה) ו  Levin (בקצרה).

 

סטיבן קוק (Steven Cook)  נולד בבאפלו, ניו-יורק בשנת 1939. בשנת 1957 החל בלימודיו באוניברסיטת מישיגן ובמסגרת לימודיו התמחה במתמטיקה. הוא סיים את התואר הראשון בשנת 1961. את התואר השני סיים באוניברסיטת הארווארד בשנת 1962 והמשיך במסלול לדוקטורט אותו סיים בשנת 1966 .

קוק עסק בתחום שנקרא "תחשיב פסוקים" (propositional calculus) העוסק בקביעת אמת לוגית של פסוק. פסוק שעבורו קיימת השמה שהופכת אותו לפסוק אמת נקרא "ספיק".

למשל :  

הפסוק (x AND y) הוא פסוק אמת אם ערכי שני המשתנים true, ולכן הפסוק ספיק.
הפסוק (
x AND NOT y) הוא פסוק אמת לכל הצבה של המשתנים, ולכן בודאי שהוא ספיק.
לעומתם הפסוק (
x AND NOT y AND NOT x) אינו ספיק שכן לא קיימת הצבה בה הוא יהיה true.

 

קוק  חקר אלגוריתמים שמטרתם לקבוע האם פסוק הוא ספיק, רבים מהם דרשו מספר פעולות מסדר גודל 2n.  עובדה שגרמה לקוק להרחיב את נושא מחקרו מבדיקת אלגוריתמים לשאלת הספיקות לשאלה רחבה יותר – "אילו בעיות אנחנו בכלל מסוגלים לפתור".

 

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

הניחוש כידוע אינו דבר מוחלט (deterministic) ולכן הוא קרא לקבוצה זו Nondeterministic Polynomial כלומר בעיות שפתרונן משולב, תחילה ניחוש שהוא אינו דטרמיניסטי ואז אימות שהוא פולינומיאלי.

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

קוק קיבל פרס טיורינג ב 1982 ופרסים על תרומה להוראת מדעי המחשב בשנים 1989 ו- 1995.

 

לאוניד לוין (Leonid Levin) נולד בדנפרופטרובסק שבאוקראינה בשנת 1948. בשנת 1971 הוא הגיש את התזה שלו לדוקטורט שעסקה בסיבוכיות קולמוגורוב. למרות שוועדת ההערכה שלו אישרה את התזה הוא לא קיבל את התואר הנכסף. הסיבה הייתה פוליטית – לוין פשוט לא היה חבר במפלגה.

בהמשך כתב מאמר בו הראה שקילות בין מספר בעיות ביניהן בעיית הספיקות ומבלי להיות מודע לעבודתו של קוק הוא קרא לבעיותיו בעיות כלליות (universal). בשנת 1978 היגר לארצות הברית וכיום הוא משמש כחבר בסגל אוניברסיטת בוסטון.

 

מקורות

Denis Shasha and Cathy Lazere. Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists, NY: Copernicus, 1995, pp. 139-156.

http://www.claymath.org/millennium

http://www.geocities.com/movie_starzz/BenandMatt/goodwillhunting.txt

מידע נוסף על קוק   http://www.cs.toronto.edu/DCS/People/Faculty/sacook.html

מידע נוסף על לוין    http://www.cs.bu.edu/fac/lnd

מידע נוסף על קולמוגורוב  http://www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Kolmogorov.html

 

חזרה לעמוד הראשי