NP
מתוך ויקיפדיה, האנציקלופדיה החופשית
NP (או: Non-Deterministic Polynomial Time) היא מחלקת סיבוכיות חשובה של בעיות במדעי המחשב.
[עריכה] הגדרת המחלקה NP
ההגדרה הנפוצה למחלקה NP היא מחלקת הבעיות אשר פתרונותיהן ניתנים לבדיקה באופן יעיל (כלומר, בזמן ריצה פולינומיאלי). הגדרה שקולה, שקודמת מבחינה היסטורית של המחלקה היא כקבוצת כל הבעיות שניתנות לפתרון יעיל באמצעות מכונת טיורינג אי דטרמיניסטית. מכונה כזו היא מכונה שיכולה בכל צעד "לנחש" מה עליה לעשות, ומובטח לה כי הניחוש תמיד "יצליח" (כלומר, יסייע למצוא את הפתרון אם פתרון קיים).
לדוגמה, בהינתן קבוצה של מספרים שלמים, נדרש לקבוע האם ניתן לחלקה לשתי קבוצות של מספרים כך שסכומן זהה (בעיה זו נקראת Partition). לדוגמה, הקבוצה {1, 3, 4, 5, 8, 11} ניתנת לחלוקה לשתי קבוצות: הקבוצה {11, 5} והקבוצה {1, 3, 4, 8}, שסכום כל אחת מהן הוא 16. מאידך, הקבוצה {1, 3, 5, 6} לא ניתנת לחלוקה כזו.
ניתן להשתכנע בקלות כי ניתן לבדוק פתרונות אפשריים לבעיה זו באופן יעיל, ולכן נמצאת בעיה זו במחלקה NP. בהינתן פתרון מוצע (חלוקה של שתי קבוצות) כל שנדרש הוא לחבר את המספרים בכל אחת משתי הקבוצות, ולבדוק האם סכומם זהה.
ההגדרה המעט יותר מדויקת של המחלקה NP היא כאוסף בעיות ההכרעה שיש עבורן אלגוריתם פולינומיאלי שיכול לבדוק הוכחות עבורן. דהיינו, לכל מופע של הבעיה אשר התשובה עבורה היא "כן" (בדוגמה לעיל: הקבוצה הראשונה), ישנה "הוכחה" קצרה (פולינומיאלית) (בדוגמה לעיל: שתי קבוצות שסכומן זהה), אשר האלגוריתם יענה עליה "כן". ואילו לכל מופע של הבעיה, אשר התשובה עבורה היא "לא" (בדוגמה לעיל: הקבוצה השניה), האלגוריתם יענה "לא" לכל הוכחה שתינתן לו.
[עריכה] השאלה P=NP?
שאלת המפתח של מדעי המחשב, הידועה כ-P=NP, היא האם כל בעיה ב-NP (דהיינו: שניתן לבדוק אותה בזמן ריצה פולינומיאלי) היא גם ב-P (דהיינו: ניתן למצוא פתרון בזמן ריצה פולינומיאלי). בדוגמה לעיל, כלל לא ברור כי בהינתן קבוצה של מספרים, ניתן למצוא באופן יעיל חלוקה לשתי קבוצות שסכומן זהה. יותר סביר להניח, ואכן זוהי ההשערה הרווחת, כי כל אלגוריתם עלול להזדקק למספר גדול יותר של צעדים (למשל: לעבור על חלק גדול מהחלוקות האפשריות, שמספרן אקספוננציאלי).
חשיבותה הגדולה של המחלקה NP ושל השאלה P=NP היא משום שבעיות נפוצות רבות (והדוגמה לעיל היא רק אחת מהן) נמצאות ב-NP, ואף פעמים רבות הינן NP-שלמות. עם זאת, לא ידוע עבורן כל אלגוריתם יעיל, וההשערה הרווחת היא שאף לא ייתכנו עבורן אלגוריתמים יעילים, ולכן כי P<>NP.
המחלקה המשלימה למחלקה NP נקראת Co-NP. מחלקה זו מכילה את כל הבעיות אשר ניתן לבדוק את שלילתן באופן יעיל. לדוגמה, לא ברור מאליו האם ניתן לבדוק באופן יעיל האם מספר הוא ראשוני (למעשה, ישנן שיטות מתקדמות לכך, אולם על פניו לא ברור כיצד לספק "הוכחה" כי מספר הוא אכן ראשוני). אולם קל למדי לספק הוכחה שמספר נתון אינו ראשוני: הוכחה כזו צריכה להכיל מחלק אחד של המספר הנתון.
מחלקה נוספת של בעיות היא NP-קשה (NP-HARD) שמכילה את הבעיות שניתן מכל בעיה L בNP לעשות רדוקציה פולינומיאלית אליהן. מחלקה זו ניתנת להגדרה גם ככל הבעיות שקשות לפחות כמו NP.
