P≠NP – מה זה אומר ואת מי זה בכלל מעניין?

מסתבר שב-HP יש יותר ממדפסות ושערויות מין של מנכ”לים. אחד ממהנדסי החברה שחרר מוקדם יותר השבוע הוכחה לבעייה מתמטית שמטרידה את קהילת המתמטיקה ומדעי המחשב קרוב ל-30 שנה. מה זה אומר ואת מי זה בכלל מעניין?

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

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

אז מה זה בכלל P נגד NP?

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

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

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

למה זה בכלל מעניין אותנו?

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

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

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

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

יניב פלדמן

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

הגב

13 תגובות על "P≠NP – מה זה אומר ואת מי זה בכלל מעניין?"

avatar
Photo and Image Files
 
 
 
Audio and Video Files
 
 
 
Other File Types
 
 
 

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

סידור לפי:   חדש | ישן | הכי מדורגים
אלעד
Guest

מעניין!
לא בטוח שהבנתי, אבל זה בכל זאת מעניין :-P

חן לבקוביץ
Guest

הבנתי, אבל שערוריית המין יותר מעניינת :-)

ברק
Guest

יש מספר טעויות בפסקה האחרונה (N במקום P).

אור
Guest

נחמד לקרוא פוסטים מהסוג הזה מידי פעם :)

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

עדי גלעד
Guest
בראיה מערכתית, הצפנה מספיק טובה, היא לא מספיק טובה. כשאנחנו מדברים על אבטחת מידע ועל סודיות, אנחנו לא רק דואגים שתוקף רנדומלי לא יקרא את המיילים שלנו. אנו חושבים על תרגילי פישינג, על הפיכת תקשורת VPN לשקופה וניתנת לקריאה, על יכולות repudiation (התחזות והתחמקות מאחריות) וכו’. אנו מדברים על כרטיסי אשראי, רכישות באינטרנט, חתימה על חוזים בין חברות ומדינות ועוד. וגם, אנחנו מפחדים מתרחישי האח הגדול. סיפורים על אשלון, על ה NSA ועל מנגנונים נוספים שמאזינים לנו בעזרת מחשבי על ויודעים לקרוא את התעבורה שלנו גם אם היא מוצפנת. ולכן, PGP היא טובה ברמה מסויימת, אבל ברמת קונספט, ברמת העיקרון,… Read more »
אור
Guest

מה זה Absolute trusty protection?

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

http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/

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

מייק
Guest

תודה על העדכון – מסוג החדשות המרעישות באמת. עבורי לפחות.

אלחי
Guest

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

אורי
Guest

קישור להוכחה?

איגור
Guest
אם P=NP, סוף העולם קרוב מתמיד. במקרה הזה ניתן יהיה ליצור רובוטים שיסתגלו לסביבה, ילמדו ויקבלו החלטות ברמה של בני אדם, ויבצעו את מה שהוטל עליהם בצורה מושלמת וללא רגע של מנוחה, ובעצם יחליפו את הכוח עבודה האנושי. עד כאן נשמע טוב, נכון? עכשיו תארו לעצמכם שאיזה פסיכי ו/או מחבל רוצה לירות לכל עבר ולהרוג כמה שיותר. הוא לא צריך לקום מהכורסה שלו. רק לרכוש איזה רובוט כזה. תארו לעצמכם שמישהו יותר פסיכי רוצה בכלל להשמיד את האנושות. לא תהיה לו בעייה להטיל את המשימה לרובוט, שייצר רובוטים אחרים, מטוסים/ספינות ופצצות גרעין. נכון,זה נשמע קצת לא מציאותי נכון לעכשיו, אבל… Read more »
wpDiscuz

תגיות לכתבה: