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-קשה היא בעיית הסכומים החלקיים: בהינתן קבוצה של מספרים שלמים, האם קיימת תת-קבוצה לא ריקה שלהם שסכומה אפס?
דוגמה נוספת היא בעיית הסוכן הנוסע: מציאת המסלול הקצר ביותר המבקר בכל הקודקודים בגרף ממושקל נתון.
בעיית העצירה היא דוגמה לבעיה שהיא NP-קשה אבל לא NP-שלמה (ואפילו לא כריעה).
קישורים חיצוניים
- String Module Error: Target string is empty.html NP-קשיות, באתר MathWorld (באנגלית) המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.
הערות שוליים
| מחלקות סיבוכיות חשובות (נוספות) | ||
|---|---|---|
| נחשב מעשי | NL • P • ZPP • RP • BPP • BQP • PTAS • APX | |
| ככל הנראה בלתי מעשי | NP • NP-קשיות • co-NP • PP • #P • PSPACE | |
| נחשב כבלתי מעשי | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL | |
| היררכית מחלקות | ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק | |
| משפחות של מחלקות | מערכת הוכחה אינטראקטיבית • DTIME • NTIME • DSPACE • NSPACE | |