P≠NP!

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

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

אני אציג את הבעיה שמוכיחה כי P שונה מ-NP. הואיל ו-P מוכל בתוך NP (או: חלקִי ל-NP), מביני עניין כבר יודעים לומר שאני מתכוון לכך שהבעיה שאציג שייכת ל-NP אבל לא ל-P.

בעית השדכנית

בעית השדכנית היא בעיה חשובה מאוד. הבעיה מטפלת בחייהם של מיליוני אנשים בעולם, כולל אנשים שאינם מתעניינים בשאלה הרת הגורל האם P=NP.

הבעיה: התאמת איש ואישה מתוך מבחר של גברים ונשים תחת התנאים הבאים:

א. יחס חד-חד-ערכי,

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

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

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

הוכחה פורמלית:

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

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

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

אבל – עדיין רב הביקוש לשדכניות (נכון לשנת 2009) למרות שקיימים מחשבים חזקים, בסתירה להנחת השלילה.

מ.ש.ל

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

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

—

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

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