על הבעיה הקשה של מלכות השחמט והבעיה הקשה עוד יותר של מלקות התקשורת

נפתח עם התיאור הקולע ביותר שראיתי מימי של הקשר הבעייתי בין מדע ותקשורת, פרי מכחולו ועטו של חורחה צ’ם, היוצר של PHD Comics:

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

ואז מגיעה התקשורת. הו, התקשורת.

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

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

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

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

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

Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers to find a solution to a "simple" chess puzzle which could, in fact, take thousands of years to solve and net a $1m prize.

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

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

מדענים באוניברסיטת סנט אנדרוז שבסקוטלנד הוכיחו שמציאת פתרון להכללה של "חידת שמונה המלכות" בשחמט תחולל מהפכה בעולם מדעי המחשב. חידת שמונה המלכות דורשת מהשחקן למקום בלוח שחמט רגיל, של 8x8 משבצות, שמונה מלכות שחמט בצורה כזו שאף מלכה לא יכולה להכות מלכה אחרת על פי חוקי השחמט - כלומר, אין שתי מלכות באותה השורה, הטור או האלכסון.   החידה נוסחה ונפתרה כבר בשנת 1850, והתברר כי קיימים לה 92 פתרונות שונים, אולם ניתן להכליל את החידה ללוח מכל גודל שהוא, לא רק 8x8. למשל, אפשר לחפש דרך להציב תשע מלכות שחמט בלוח 9x9, או עשר מלכות שחמט בלוח 10x10 וכן הלאה. אפשר גם לשאול את השאלה הבאה - בהינתן לוח מגודל כלשהו שכבר הונחו עליו חלק מהמלכות, האם קיימת דרך להוסיף את יתר המלכות בצורה שתניב פתרון לחידה, בדומה לאופן שבו בסודוקו משלימים לוח שכבר חלק מהמספרים נתונים בו?   המדענים הוכיחו כי החידה המוכללת הזו היא מה שמכונה בעולם מדעי המחשב בעיה NP-שלמה. זה אומר שמצד אחד, אם נתון לוח שעליו חלק מהמלכות ומישהו טוען שבידיו פתרון למקרה זה של החידה, קל לו להוכיח את זה - הוא פשוט מציב את המלכות הנותרות על הלוח ואז קל לבדוק שהפתרון שלו נכון. מצד שני, קיום שיטה כללית למציאת פתרון לבעיה יהיה בעל השלכות מרחיקות לכת על מדעי המחשב: ניתן יהיה "לתרגם" אינספור בעיות מהותיות מעולם מדעי המחשב לבעייה בסגנון חידת המלכות, ופתרון של בעיית המלכות יניב פתרון לבעיות המקוריות.   כך למשל אם מישהו מעוניין לפרוץ מערכת הצפנה המבוססת על שיטת RSA הוא יוכל לתרגם את פרטי מערכת ההצפנה לבעיית שחמט, ואם יצליח למצוא פתרון לבעיית השחמט הוא יוכל לתרגם את הפתרון הזה חזרה לפיצוח של מערכת ה-RSA. בשל כך מציאת פתרון יעיל לבעיית השחמט יהיה בעל השלכות מרחיקות לכת על עולם מדעי המחשב.   בעיית חידת השחמט היא רק מקרה אחד מבין אלפים רבים של בעיות NP-שלמות המוכרות לנו כיום. אחת מהשאלות הפתוחות המרכזיות במדעי המחשב, הנקראת שאלת P=NP, היא השאלה האם קיימת בעיה NP-שלמה שקיים עבורה פתרון יעיל. האמונה הרווחת בקרב המומחים היא כי פתרון יעיל שכזה אינו קיים, אבל כל נסיונות ההוכחה לכך מאז שהשאלה נוסחה בשנות השבעים לא צלחו. שאלת P=NP היא אחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה ועל כן מי שיפתור אותה לחיוב או לשלילה יזכה במיליון דולר.  

זהו בערך. עכשיו אני אתייחס טיפה יותר בפירוט טכני לעניינים שיש פה.

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

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

מהסיבה הזו ומעוד סיבות טכניות שלא אכנס אליהן כרגע, מה שעושים במדעי המחשב התיאורטיים בהקשר הזה הוא אף פעם לא לדבר על בעיה בודדת ספציפית, אלא על אוסף של בעיות שתלויות באיזה שהוא פרמטר \( n \). כאן ה-\( n \) הוא מספר המלכות והאורך והרוחב של הלוח. כלומר, אנחנו מתעניינים בשאלה הכללית של איך אפשר לשים \( n \) מלכות על לוח מגודל \( n\times n \), עבור כל \( n \). עכשיו כבר אי אפשר פשוט לשמור פתרונות כחלק מהקוד ולהדפיס אותם כי הקוד צריך לדעת להתמודד עם אינסוף מקרים שונים, והוא לא יכול פשוט לכלול פתרונות לכולם (קוד הוא מאורך סופי). הקוד חייב לבצע חישוב כלשהו שמאפשר לו לייצר פתרונות, ואז אפשר למדוד את הזמן של החישוב הזה ולהגיד איך הזמן הזה גדל ככל ש-\( n \) גדל. אם הגדלה של \( n \) פי 2 מגדילה את זמן החישוב פי 2, או פי 4, או פי 8, זה יחסית סביר; לכזה דבר קוראים “זמן פולינומי” (לא אכנס להגדרה המלאה). לעומת זאת אם הגדלה של \( n \) ב-\( 1 \) מגדילה את זמן החישוב פי 2, זה כבר לא סביר בעליל ונקרא “זמן אקספוננציאלי”. לאוסף הבעיות במדעי המחשב שאפשר למצוא להם פתרון ביעילות קוראים P.

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

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

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

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

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