NP (מחלקת סיבוכיות) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
מ הגהה |
||
שורה 63:
מבין הבעיות ה-NP-קשות, החשובות ביותר הן אלו אשר שייכות בעצמן למחלקה NP. בעיות אלו מכונות '''NP-שלמות'''. בשל תכונת הקושי שלהן, השאלה אם P=NP קמה ונופלת על כל אחת מבעיות אלו - אם עבור בעיה NP-שלמה אחת ניתן יהיה להוכיח כי היא ב-P, אז P=NP; ולחלופין, אם יהיה ניתן להראות עבור בעיה NP-שלמה אחת כי היא אינה שייכת ל-P הדבר יגרור כי P≠NP.
אין זה מובן מאליו שבעיות NP-שלמות קיימות כלל; הדבר הוכח בשנת [[1971]] בידי [[סטיבן קוק]], שגם הגדיר את מחלקת הבעיות ה-NP-שלמות (אך לא השתמש בשם זה, שניתן בידי [[ג'ון הופקרופט]] בשנת [[1972]]) והראה כי [[בעיית SAT|בעיית הספיקות של נוסחאות מצורת CNF]] ("בעיית SAT") היא NP-שלמה. הוכחה דומה ניתנה באופן בלתי תלוי בברית המועצות בידי [[ליאונרד לוין]], ותוצאה זו נקראת כיום [[משפט קוק-לוין]]. ההוכחה כי SAT היא NP-שלמה היא ישירה - בהינתן בעיה כלשהי ב-NP, מראים כיצד ניתן לבנות רדוקציה ממנה אל SAT (כלומר, לבנות נוסחה שמתארת, במובן מסוים, את הבעיה). לאחר שהוכח כי SAT היא NP-שלמה נסללה הדרך להראות עבור בעיות רבות נוספות כי הן NP-שלמות, שכן כדי להראות כי בעיה
=== רשימת 21 הבעיות ה-NP-שלמות של קארפ ===
| |||