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, אולם זו אינטואיציה ולא רעיון מבוסס.

שלח מאמר זה באימייל שלח מאמר זה באימייל
הדפס מאמר זה הדפס מאמר זה

2 תגובות ל“P≠NP!”

  1. מאת דביר:

    אהבתי,
    למרות הכשל הלוגי העמוק בהוכחה.

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

  2. מאת tsabar:

    דביר אתה תותח.

השארת תגובה