NP-קשה
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת הסיבוכיות, בעיית הכרעה נקראת NP-קשה (Non-Deterministic Polynomial-Time Hard או בקיצור NP-HARD) אם קיימת רדוקציה פולינומית אליה מכל בעיית הכרעה ששייכת ל-NP. במילים אחרות, בעיה היא NP-קשה, אם היא קשה לפחות כמו כל אחת מהבעיות ב־NP. כאשר בעיה גם שייכת למחלקה זו, והיא גם NP, אומרים עליה שהיא NP-שלמה.
אם עבור בעייה NP-קשה כלשהי הייתה לנו אורקל, מכונת קסם שיודעת לפתור בזמן פולינומיאלי את אותה בעיה, היינו יכולים להשתמש בה ולהגדיר באמצעותה אלגוריתם בעל זמן ריצה פולינומיאלי לפתרון כל בעיית NP. מכאן נובע, שאם היה בידינו אלגוריתם בעל זמן ריצה פולינומיאלי לבעיה NP-קשה אחת, היינו מוכיחים שמתקיים P=NP.
[עריכה] דוגמאות לבעיות NP-קשות
ישנן בעיות הכרעה רבות שידועות כ־NP-קשות. למשל:
- בעיית הסכום החלקי - בהינתן קבוצה של מספרים שלמים, האם קיימת תת קבוצה מתוכה שאיננה ריקה וסכומה 0?
- בעיה זו הוכחה כשייכת למחלקת הבעיות ה־NP-שלמות, ולכן ברור שהיא גם NP-קשה. עם זאת, יש בעיות NP-קשות שאינן NP-שלמות:
- בעיית העצירה - בהינתן תוכנית (או אלגוריתם) וקלט עבורה, האם היא תעצור?
- בעיה זו ידועה כבעיה שכלל לא ניתנת לחישוב. לכן קל וחומר שהיא קשה לפחות כמו כל הבעיות ב־NP, שניתנות לחישוב.
ניתן להראות שבעיית העצירה היא NP-קשה גם באופן פורמלי, על־ידי הגדרת רדוקציה פולינומית מכל בעיה ב־NP אליה. רדוקציה זו כוללת למעשה בניית תוכנית שעוצרת אם ורק אם הקלט מהווה פתרון לבעיה. יש לשים לב, שתוכנית זו לא צריכה להיות בעלת זמן ריצה פולינומיאלי; רק ההליך לבניית התוכנית צריך להיות כזה.

