איך הפכה תגלית קטנה אבל נחמדה במדעי המחשב ל"אתגר בשווי מיליון דולר" שהחוקרים התמימים לכאורה הציבו בפני חבריהם?
ככל הנראה, מדובר בשילוב של הרצון המופרז של האוניברסיטאות לחשיפה בכל מחיר, ותקשורת המיינסטרים שלא יכולה לסנן את המידע שמגיע אליה.
 
מאת גדי אלכסנדרוביץ׳.
 
לא מזמן התבשרנו בכתבה [1] באתר Ynet (וגם באתרים אחרים בחו"ל) על כך ש"מדענים באוניברסיטת סנט אנדרוז שבסקוטלנד הציבו אתגר בפני טובי המתכנתים: גלו פתרון לחידת שחמט "פשוטה" – וזכו במיליון דולר. המתכנתים יוכלו לזכות בכסף אם ימצאו פתרון יעיל לחידת שמונה המלכות המפורסמת".
 
המשפט הזה מרשים למדי בכמות השגיאות שנדחסו לכמות קטנה כל כך של מילים. לזכות Ynet ייאמר שהמשפט הזה הוא תרגום כמעט מדויק של ההודעה לעיתונות של אוניברסיטת סנט אנדרוז, כך שהאשמים האמיתיים הפעם הם מחלקת יחסי הציבור של האוניברסיטה; העיתונות הלא מדעית פשוט לא ערוכה להתמודד עם מידע שגוי שנזרק עליה מכיוון האוניברסיטאות, שכן חסרים בה אנשי מקצוע (אף כיועצים) שיכולים לסנן ולערוך בהתאם.
 
מה כן גילו המדענים מאוניברסיטת סנט אנדרוז? תוצאה נחמדה אבל לא חריגה. לא מזמן [2] תיארנו כאן את שאלת P=NP במדעי המחשב. הזכרנו שיש מחלקה מעניינת במיוחד של בעיות במדעי המחשב שנקראת "בעיות NP-שלמות" - אלו בעיות שפתרון יעיל לאחת מהן יגרור מיידית ש-P=NP, עקב העובדה שניתן "לקודד" את כל יתר הבעיות ב-NP בתור מופעים של בעיה NP-שלמה כלשהי. כיום ידועות אלפי בעיות כאלו, והחוקרים הוכיחו על בעיה אחת נוספת שהיא כזו - בעיה שהמוטיבציה הראשונית להגדרתה מגיעה ממה שנקרא "חידת שמונה המלכות".
 
בחידת שמונה המלכות, יש לשים שמונה מלכות על לוח שחמט (מגודל 8x8) בצורה כזו שאף מלכה לא מאיימת על האחרות על פי חוקי השחמט - כלומר, לאלו מאיתנו שאינם בקיאים בשחמט, שאין שתי מלכות שנמצאות על אותה שורה, טור או אלכסון. זוהי חידה נחמדה שניתנת לפעמים בתור תרגיל תכנותי (קל לכתוב תוכנית מחשב לא יעילה במיוחד שבכל זאת תצליח לגלות פתרון).
 
החוקרים עסקו בבעיה כללית יותר: כמו שאפשר לדבר על 8 מלכות ולוח 8x8 אפשר לדבר גם על 100 מלכות ולוח של 100x100 משבצות, או 1024 מלכות ולוח של 1024x1024 משבצות, ובאופן כללי n מלכות ולוח של nxn משבצות. גם בעיה זו לכשעצמה אינה קשה במיוחד - לכל n גדול מ-3 ידועה דרך להציב n מלכות על לוח nxn בצורה שתענה על תנאי החידה. עם זאת, ניתן ליצור גרסה קשה יותר של החידה באופן הבא: נניח שחלק מהמלכות כבר נמצאות על הלוח; האם יש דרך להוסיף את יתר המלכות בצורה חוקית? כדי לראות מדוע גרסה זו קשה יותר, חשבו על סודוקו: מה קשה יותר, למלא לוח ריק "מאפס", או למלא לוח שבו כבר שובצו כמה מספרים?
 
מכיוון שהחוקרים הוכיחו שהבעיה היא NP-שלמה, נובע מכך שאם היא תיפתר ביעילות, הדבר יגרור ש-P=NP - התוצאה הסנסציונית ביותר שניתן להעלות על הדעת במדעי המחשב, שאכן תזכה את הפותר במיליון דולר, שהם הפרס שהבטיח מכון קליי למתמטיקה לכל מי שיפתור אחת משבע בעיות פתוחות מרכזיות במתמטיקה ש-P=NP נמנית עמן. עם זאת, הסברה הרווחת בקרב מדעני המחשב היא ש-P כלל לא שווה ל-NP, כך שבעיית המלכות המוכללת בכלל אינה ניתנת לפתרון יעיל. גם הוכחה שהבעיה אינה פתירה תהיה תגלית מופלאה ותזכה את המוכיח במיליון דולר, אבל האתגר הזה הוא כביר; לא מזמן התבשרנו על עוד ניסיון הוכחה מאת חוקר רציני במדעי המחשב שהתגלו בו טעויות מהותיות והחוקר נאלץ לחזור בו.
 
אם כן, המשפט של Ynet שצוטט לעיל שגוי בשלל דרכים: הבעיה אינה למצוא פתרון יעיל לחידת שמונה המלכות אלא לחידה אחרת, קשה משמעותית יותר. לחידת שמונה המלכות כבר קיים פתרון יעיל; המדענים המעורבים לא הציגו שום אתגר לאף אחד; אכן קיים פרס של מיליון דולר אבל הוא לא קשור לאוניברסיטת סנט אנדרוז; ונראה מאוד לא סביר שניתן יהיה לזכות בפרס על ידי מציאת פתרון יעיל אלא בדיוק ההפך, על ידי ההוכחה שפתרון כזה אינו קיים.
 
מדעי המחשב יכולים להיות מעניינים דיים גם ללא כותרות סנסציוניות הזויות.
 
גדי אלכסנדרוביץ' הוא בעל ד"ר למדעי המחשב מהטכניון וכותב הבלוג "לא מדויק".
 
לקריאה נוספת:
https://goo.gl/oFqEpY