בעיית P=NP
בעיה במדעי המחשב / ויקיפדיה האנציקלופדיה encyclopedia
השאלה האם P=NP היא בעיה פתוחה מרכזית במדעי המחשב, העוסקת ביכולת לפתור אוסף גדול של בעיות בצורה יעילה. במילים פשוטות, השאלה היא האם כל בעיה שניתן לבדוק עבורה בצורה יעילה האם פתרון מוצע הוא נכון, היא גם בעיה שניתן למצוא עבורה פתרון בצורה יעילה.[1]
ההגדרה ליעילות בהקשר של בעיות מהמחלקות P ו-NP מתייחסת לקיום אלגוריתם שפותר את המשימה בזמן פולינומי, כלומר זמן השלמת המשימה משתנה כפונקציה פולינומית ביחס לגודל הקלט לאלגוריתם.
המחלקה P היא מחלקת סיבוכיות המכילה את כל בעיות ההכרעה אשר ניתנות לפתרון באופן יעיל, כלומר בזמן ריצה פולינומי. לחלק מבעיות ההכרעה לא קיים אלגוריתם ידוע שמאפשר לפתור אותן באופן יעיל, אך כן קיים אלגוריתם שבהינתן תשובה, יוכל לאמת אותה ביעילות. המחלקה הכוללת את הבעיות הללו, שבהינתן פתרון שלהן ניתן לאמת אותו בזמן פולינומי, נקראת NP.
תשובה לשאלה האם P שווה ל-NP תקבע האם ניתן לפתור בזמן פולינומי בעיות שניתן לאמת פתרון שלהן בזמן פולינומי. אם P≠NP, בהתאם להשערה הרווחת, פירוש הדבר הוא שישנן בעיות שנמצאות ב-NP אך לא נמצאות ב-P, כלומר קיימות בעיות שקשה למצוא להן פתרון ולא ניתן לפתור אותן בזמן פולינומי, אך ניתן לאמת פתרון מוצע לבעיה בזמן פולינומי.
לפתרון הבעיה ישנן השלכות תאורטיות ומעשיות רבות, והיא זכתה להכרה כאחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה.