NP-קשיות

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף NP-קשה)
קפיצה אל: ניווט, חיפוש

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

הגדרה[עריכת קוד מקור | עריכה]

בעיית הכרעה H היא NP-קשה אם ניתן לעשות רדוקציה בזמן פולינומי מכל בעיה L ב-NP ל-H.

דוגמאות[עריכת קוד מקור | עריכה]

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

דוגמה נוספת היא בעיית הסוכן הנוסע: מציאת המסלול הקצר ביותר המבקר בכל הקודקודים בגרף ממושקל נתון.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. 1998. ISBN 0262720140. OCLC 247934368. 
  2. ^ Knuth, Donald (1974). "Postscript about NP-hard problems". ACM SIGACT News 6 (2): 15–16. doi:10.1145/1008304.1008305. בדיקה אחרונה ב-30 בינואר 2016.