החומר המופיע בעמוד זה פורסם לראשונה בכתב העת "הבטים בהוראת מדעי המחשב" גליון מרץ 1995, עמודים 11-17

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

על סיבוכיות חישובית ואופייה של הדיסציפלינה "מדעי המחשב"

On Computational Complexity and the Nature of  Computer Science

Juris Hartmanis

 

Juris Hartmanis הוא פרופסור להנדסה במחלקה למדעי-המחשב באוניברסיטת קורנל. תחומי המחקר שלו מתמקדים בתיאוריה של חישוב, סיבוכיות חישובית וסיבוכיות מבנית. בשנת 1993 הוענק לו (במשותף עם Richard Stearns) הפרס על-שם Turing לשנת 1993. הפרס מוענק מדי שנה (מאז 1966) לאדם שתרם תרומה מיוחדת ובעלת חשיבות לדיסציפלינה של מדעי המחשב. במעמד של חלוקת הפרס, נשא הרטמניס הרצאה, שבה סקר את הרקע שלו, התייחס לעבודתו הנוכחית והציג את עמדתו לגבי אופייה של הדיסציפלינה "מדעי-המחשב". נביא כאן תקציר של ההרצאה, כפי שפורסמה בגיליון אוקטובר 94 (Vol. 37) של הירחון Communication of ACM, בעמודים 37-43.

 

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

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

 

דרכו של הרטמניס למדעי המחשב, לא הייתה ישירה ובדיעבד היא נראית כמעט אקראית.

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

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

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

 

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

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

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

 

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

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

 

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

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

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

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

 

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

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

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

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

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

 

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

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

P¹NP¹ PSPACE¹EXPTIME¹NEXPTIME¹EXPSPACE ?

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

 

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

 

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

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

 

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

כדבריו של  Fred Brooks  על תכנות,

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

 

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

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

 

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

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

 

Warren McCullach ראה בעיני רוחו כבר ב- 1964 אפיסטמולוגיה מחקרית, העוסקת באופן אחסונו של הידע במוח ובאפשרות לאחסנו במכונה. ואילו John McCarthy  טען שהמחקר באינטליגנציה מלאכותית יכול להוביל למעין מטה-אפיסטמולוגיה שתהיה אנלוגית למתמטיקה. למחקר של היחסים בין חוק המאפשר למומחה לקבל ראייה, לבין העולם בו הוא נמצא. מחקר כזה יכול להוביל לתוצאות מתימטיות שיאפשרו לבחון האם אסטרטגיות אינטלקטואליות מסוימות יכולות להוביל לגילוין של עובדות מסוימות על העולם. אפשרות זו תביא בסופו של דבר למהפכה פילוסופית.

 

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

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

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

 

תורת הפונקציות הרקורסיביות, שקיבלה את תנופתה הראשונית מעבודתו של Gödel  על אי-ספיקה, איפשרה לסווג את הבעיות לפי האפשרות לחשב אותן ביעילות, ולכן גם הראתה בברור את העוצמה והמגבלות של הגיון מתמטי פורמלי. תורת הסיבוכיות נאבקת כיום כדי לקבוע, איזו בעייה ניתנת לחישוב יעיל ואיזו בעייה אינה ניתנת לחישוב כזה. במסגרת מאמצים אלה, בעיית P=NP? היא הבעיה הפתוחה הידועה ביותר, אך אינה היחידה. כאשר בעייה זו ובעיות פתוחות נוספות ימצאו את פתרונן, וכאשר נבין טוב יותר את הגבולות של מה שניתן לחישוב, או אז יאפשרו לנו הדיסציפלינה של מדעי המחשב ותורת הסיבוכיות להבין טוב יותר את העוצמה ואת המגבלות של ההגיון אדם-מחשב (man-computer reasoning) .

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

 

מקורות:

[1] Turing, A.M. On computable numbers with an application to the Entscheidunga problem. In Proceedings of the London Mathematical Society, series2, 42 (1936), 230-265.

[2] Hartmanis, J. and Stears, R. F. On Computational complexity of algorithms. Trans. Amer. Math. Soc. , 177 (1965), 285-306.

 

חזרה לאתר המרכז הארצי

חזרה לאתר הבטים

חזרה לגליון מרץ 95

חזרה לתחילת העמוד