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

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

phd051809s

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

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

אני אוהב מקרים כאלו. הם נותנים לי תירוץ לכתוב פוסטים על נושאים שבדרך כלל לא הייתי כותב עליהם פוסטים, ועכשיו יש לנו מקרה חם מהתנור. יש חידה מפורסמת בשם "חידת 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 על הנושא הזה? אוקיי. ככה:

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

 

החידה נוסחה ונפתרה כבר בשנת 1850, והתברר כי קיימים לה 92 פתרונות שונים, אולם ניתן להכליל את החידה ללוח מכל גודל שהוא, לא רק 8×8. למשל, אפשר לחפש דרך להציב תשע מלכות שחמט בלוח 9×9, או עשר מלכות שחמט בלוח 10×10 וכן הלאה. אפשר גם לשאול את השאלה הבאה – בהינתן לוח מגודל כלשהו שכבר הונחו עליו חלק מהמלכות, האם קיימת דרך להוסיף את יתר המלכות בצורה שתניב פתרון לחידה, בדומה לאופן שבו בסודוקו משלימים לוח שכבר חלק מהמספרים נתונים בו?

 

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

 

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

 

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

 

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

ראשית כל, חידת המלכות היא בדיוק מה שתיארתי ב"כתבה": יש לוח 8×8, צריך להניח עליו 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-שלמות הידועות, אבל אין כאן סנסציה. אין כאן שום דבר מרגש ממש, ולכן האוניברסיטה נקטה בכאלו מהלכי יחסי ציבור הזויים כדי לפרסם אותו.

45 תגובות על הפוסט “על הבעיה הקשה של מלכות השחמט והבעיה הקשה עוד יותר של מלקות התקשורת

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

  2. אני לא מניח פתרון יחיד. אם יש יותר מפתרון אחד, הגישה שלי תמצא אחד מהם.

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

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

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

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

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

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

  8. למיטב ידיעתי, פירוק לגורמים היא לא בעית NP שלמה. כלומר, "אפשר לקודד את הפיצוח של מערכת RSA" זה לא בדיוק כמו לומר ש P≠NP

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

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

    אם שואלים אותי על לוח בגודל כלשהו, למשל לוח בגודל 85×85 משבצות, ועליו 85 מלכות, מה המינימום שאני צריך לעשות כדי לזכות בפרס?

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

    2. לתת מספר מדוייק של כמות הפתרונות הנכונים שקיימים עבור הלוח הנ"ל?

    3. לתת רשימה של כל הפתרונות האפשריים עבור הלוח הנ"ל?

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

  11. ל"לא מתמטיקאי":
    אני מניח שהם התכוונו (בYNET) שזו אחת משבע בעיות המילניום https://he.wikipedia.org/wiki/%D7%91%D7%A2%D7%99%D7%95%D7%AA_%D7%94%D7%9E%D7%99%D7%9C%D7%A0%D7%99%D7%95%D7%9D_%D7%A9%D7%9C_%D7%9E%D7%9B%D7%95%D7%9F_%D7%A7%D7%9C%D7%99%D7%99
    (השישית ליתר דיוק)
    פתרון יעיל של בעיה זו יפתור את הבעיה השישית (ועוד לחיוב) כך שאפשר לומר ש"בין הפותרים נכונה יוגרלו מליון דולר לכל אחד"
    הוכחה שאין פתרון יעיל, אינה תזכה בפרס, זאת כיוון שחשבו שמציאת דוגמה נגדית יכולה להתבצע בכוח גס אבל הוכחה תדרוש באמת כשרון יוצא דופן

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

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

  13. ל"לא מתמטיקאי":

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

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

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

    האמונה הרוווחת (והמבוססת) בקרב העוסקים בתחום היא שדווקא המקרה השני הוא מה שיתרחש בפועל – שפשוט לא קיים אלגוריתם יעיל עבור הבעיות הללו.

    החוקרים של סנט אנדרוז *לא* הציעו פרס. כל מה שהם עשו היה להוכיח שבעיה מסויימת (לא חידת 8 המלכות) היא בעלת התכונה שדיברתי עליה למעלה – פתרון יעיל עבור הבעיה הזו יוכיח ש-P=NP והוכחה שאין פתרון כזה תוכיח ש-P שונה מ-NP.

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

  14. ולשאלת ההמשך שלך – אתה צריך להציג אלגוריתם שמקבל לוח מגודל n *כלשהו*, וכבר שמו עליו מספר *כלשהו* של מלכות, ולומר אם יש דרך להוסיף עוד מלכות ללוח כך שיהיו בו n מלכות שלא מאיימות אחת על השניה. האלגוריתם שלך צריך לעבוד ביעילות *תמיד*, לכל קלט.

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

    לפיכך אני מניח שידוע שמספר הפתרונות סופר־פולינומיאלי ב-n?

  16. גדי, תודה על התשובה זה נשמע מרתק! ברשותך יש לי שתי שאלות המשך:

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

    2. לפי מה שידוע לך, מה גודלו המקסימאלי של לוח שחמט שמחשב מסוגל לפתור היום? 500×500 משבצות? 1000×1000 משבצות? אם מישהו יציג אלגוריתם שנותן (נגיד תוך מספר שעות) **פיתרון אחד נכון** עבור כל לוח שגודלו עד 2500×2500 משבצות שכבר הוצבו עליו חלק מהמלכות, האם הוא לא יהיה זכאי לפרס? "לוח בכל גודל" נשמע לי מעורפל מדי… בטח יש איזה גודל מינימלי שמי שיציג פיתרון עבורו יהיה זכאי לפרס, מהו הגודל המינימלי הזה?

    תודה מראש.

  17. שאלת המשך לשתי השאלות הקודמות –

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

    אשמח מאד לתשובה על שלושת השאלות, תiדה.

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

  18. נתקלתי בסרטון יוטיוב של אדם שטוען כי פונקצייה קצרה בת 6 שורות קוד נותנת עבור כל לוח בגודל n את מספר הפתרונות שקיימים עבור הלוח הנ"ל, לדוגמא בדקה 26:15 הוא מכניס כקלט 8×8 ומקבל כצפוי שמספר הפתרונות הוא 92:

    https://www.youtube.com/watch?v=u6viVC1fJ9g

    מה דעתך? זה בעצם עונה לאתגר לא?

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

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

    לגבי 3, לא הבנתי את השאלה. מה זה אומר "פתרון של הלוח" אם לא כזה שמביא בחשבון את המלכות שכבר עליו?

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

  20. גדי תודה,

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

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

    3. הכוונה שלי היא שנגיד ויש לוח בגודל מסויים שיש עבורו 850 פתרונות אפשריים, האם יכול להיות שיציבו לי על הלוח 848 מלכות שעונות לתנאי (לא מאיימות על אף מלכה אחרת) אבל לא מאפשרות להציב את 2 המלכות הנותרות? זו הייתה השאלה.

  21. ״לא מתמטיקאי״, הרעיון של הפרס, ובכלל של תחום ה״סיבוכיות״ הוא שאנחנו מוכנים לתת פרסים רק על פתרונות שיהיו רלוונטיים גם עוד 1000 שנה ולא רק בהווה. בוא נניח לרגע שמישהו באמת מצא תוכנית שעובדת טוב עבור גודל 2000 או 200000. האם הוא צריך לקבל פרס?

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

    דבר שני, אולי היום לוחות בגודל 2000 זה הכי גדול שאפשר לחשוב עליו, אבל אולי עוד 50-100 שנה אנשים ירצו לוחות בגודל 20000 או 200000? אם מישהו ימצא תוכנית מחשב שלוקח לה עשר שניות על לוח בגודל 2000 אבל לוקח לה טריליון שנה על לוח בגודל 3000, הוא לא אמור לקבל פרס כי בעתיד הפתרון הזה כבר לא יהיה רלוונטי (אפילו אם יהיו לנו מחשבים קצת יותר טובים). זה בסדר אם זמן הריצה גדל באופן ״צנוע״ כשמגדילים את הקלט (גדי הסביר את הנושא הזה בפוסט שלו קצת). כדי לקבל את הפרס אתה צריך להוכיח לא רק שתוכנית המחשב שלך תמיד צודקת, אלא שהזמן שלוקח לי לחשב את הפתרון אף פעם לא ״קופץ בהרבה״ כשמגדילים את הקלט. לא במעבר מלוח בגודל 2000 ל- 3000 ולא במעבר מלוח בגודל 100000000 ל- 100001000.

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

  22. רגיסטר,

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

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

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

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

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

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

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

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

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

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

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

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

  29. יוסי הלבן,

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

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

  30. יוסי,

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

  31. יוסי השחור,

    ״בנוגע לשאלתך האחרונה – בהחלט כן, אחרת זה היה ממש קל״

    למה אתה מתכוון כשאתה אומר ״אחרת זה היה ממש קל״? הם כיום יש לך אלגוריתם שיודע לפתור את בעיית המלכות (אפילו על מחשב על) תוך פחות מיום עבור לוח בגודל 3500×3500 משבצות?

  32. שלום גדי,
    קודם כל אחלה בלוג !
    אז ככה – אני איש תוכנה ואלגוריתמים אבל בלי חיבור ורקע מיוחד במתמטיקה, ואני מוצא שהבלוג שלך מאוד מעניין – לדעתי אכנס אליו לא מעט בזמן הקרוב.
    ראיתי את הכתבה ב ynet והבנתי כנראה שמדובר בחוסר דיוק במקרה הטוב וקשקוש מוחלט במקרה הפחות טוב (לפי הפוסט שלך – יצא משהו באמצע, קצת יותר קרוב לקשקוש :) )
    אבל בכל אופן זה עשה לי חשק – אז ישבתי כשעתיים אתמול בלילה וכתבתי אלגוריתם (כמובן לא רקורסיבי-דטרמינסטי – אלא כזה שמבוסס על הערכת מצבים ומימד אקראיות) והוא הצליח לפתור שמונה מלכות בלוח של 8X8 בשניה, ו 100 מלכות על לוח של 100X100 כבר לקח לו 8 דקות – נכנסתי עוד פעם ל ynet כדי לראות איפה אני לוקח את המליון דולר :) ואחד הטוקבקים הפנה אותי לבלוג המצוין שלך, והבנתי את מה שניחשתי כבר – הרבה עושר לא יצא מזה …

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

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

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

  33. אז אם כך השאלה שלי, למה הבעיה הזו נשארה פתוחה ?
    למה אין אפשרות לתת הוכחה חותכת ש P != NP ?

  34. נעם ולא מתמטיקאי

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

    ועכשיו למשימה העומדת בפניכם – עליכם למצוא אלגוריתם יעיל כזה לבעית הצבת המלכות על הלוח, כלומר שאם יש לכם פתרון ללוח של 100 על 100 בנניח 1000 צעדים אזי מספר הצעדים של האלגוריתם שלכם לא יתחיל לזנק בסדר גודל של פי 10 נניח בכל פעם שאתם מגדילים את הלוח ל 101 על 101,ל 102 על 102 וכולי.

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

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

  35. השאלה האמיתית היא לא למה קשה להוכיח ש-P != NP אלא למה בכלל נראה לנו סביר שאפשר יהיה להוכיח משהו כזה. הוכחה כזו צריכה להראות עבור בעיה מסויימת ש*אף* אלגוריתם לעולם לא יפתור אותה ביעילות. לא משנה כמה חכמים נהיה. לא משנה איזה טריקים מתמטיים מדהימים נמציא בעתיד. לא משנה אילו גישות חדשות לחלוטין לאופטימיזציה נגלה. לא משנה כמה יצירתיים נהיה. לא משנה אם בעתיד יהיו לנו מאות אלפי גאונים מסדר הגודל של איינשטיין שיקדישו את כל חייהם רק כדי למצוא פתרון יעיל לזה וישתמשו בכל היצירתיות שעומדת לרשותם. לא משנה אם בעתיד יהיה לנו כוח חישוב גדול פי גוגול מאשר יש לנו כיום וכולו יוקדש למציאת פתרון יעיל לבעיה. כל זה לא יעבוד. שום דבר לא יעבוד. אף פעם. לעולם.

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

כתיבת תגובה

האימייל לא יוצג באתר.