https://www.yisraelpedia.com/index.php?action=history&feed=atom&title=NP-%D7%A7%D7%A9%D7%99%D7%95%D7%AANP-קשיות - היסטוריית גרסאות2026-09-14T13:33:56Zהיסטוריית הגרסאות של הדף הזה בוויקיMediaWiki 1.43.8https://www.yisraelpedia.com/index.php?title=NP-%D7%A7%D7%A9%D7%99%D7%95%D7%AA&diff=512325&oldid=previmported>AutoMod: תווי יוניקוד סמויים2025-07-14T04:59:41Z<p>תווי יוניקוד סמויים</p>
<p><b>דף חדש</b></p><div>'''NP-קשיות '''([[NP (מחלקת סיבוכיות)|NP]] קשה), היא מחלקה של בעיות ב[[תורת הסיבוכיות]], שהן, באופן לא פורמלי, "קשות לפחות כמו הבעיות הקשות ביותר ב-[[NP (מחלקת סיבוכיות)|NP]]". באופן מדויק יותר, נאמר שבעיה H היא NP-קשה, אם ניתן לעשות [[רדוקציה חישובית|רדוקציה]] ב[[זמן פולינומי]] מכל בעיה L ב-NP ל-H. כלומר: אם נניח שהפתרון של H לוקח יחידת זמן אחת, אז ניתן לפתור את L (תוך שימוש בפתרון ל-H) בזמן פולינומי.{{הערה|שם=Leeuwen|{{Cite book|url=http://www.worldcat.org/title/algorithms-and-complexity/oclc/247934368/viewport|title=Handbook of Theoretical Computer Science|publisher=Elsevier|year=1998|isbn=0262720140|editor-link=Jan van Leeuwen|volume= A, Algorithms and complexity|location=Amsterdam|oclc=247934368}}}}{{הערה|{{Cite journal|url=http://doi.acm.org/10.1145/1008304.1008305|title=Postscript about NP-hard problems|last=Knuth|first=Donald|date=1974|journal=ACM SIGACT News|issue=2|doi=10.1145/1008304.1008305|volume=6|pages=15–16|access-date=30 January 2016}}}} בעיה שהיא NP-קשה אינה בהכרח בעיה ב-NP, שכן ייתכן שלא קיימת [[מכונת טיורינג לא-דטרמיניסטית]] המסוגלת להכריע אותה בזמן פולינומי, אך עדיין ניתן לבצע אליה רדוקציה בזמן פולינומי מכל בעיה ב-NP. בעיה שהיא NP-קשה וגם ב-NP היא בעיה NP-שלמה.<br />
ההנחה הרווחת כיום היא שלא קיים [[אלגוריתם]] פולינומי לבעיות NP-קשות, על אף שזוהי השערה שלא הוכחה. אם קיים אלגוריתם הפותר בעיה NP-קשה כלשהי בזמן פולינומי בגודל הקלט, אז מהגדרת המחלקה נובע ש-P=NP, כאשר המחלקה [[P (מחלקת סיבוכיות)|P]] היא מחלקת הבעיות הניתנות לפתרון בזמן פולינומי בגודל הקלט.<br />
<br />
== הגדרה ==<br />
[[בעיית הכרעה]] H היא NP-קשה אם ניתן לעשות [[רדוקציה חישובית|רדוקציה]] בזמן פולינומי מכל בעיה L ב-NP ל-H.<br />
<br />
== דוגמאות ==<br />
דוגמה לבעיה NP-קשה היא [[בעיית הסכומים החלקיים]]: בהינתן קבוצה של מספרים שלמים, האם קיימת [[תת-קבוצה]] לא ריקה שלהם שסכומה אפס?<br />
<br />
דוגמה נוספת היא [[בעיית הסוכן הנוסע]]: מציאת המסלול הקצר ביותר המבקר בכל הקודקודים ב[[גרף ממושקל]] נתון.<br />
<br />
[[בעיית העצירה]] היא דוגמה לבעיה שהיא NP-קשה אבל לא NP-שלמה (ואפילו לא כריעה).<br />
<br />
==קישורים חיצוניים==<br />
* {{MathWorld}}<br />
<br />
==הערות שוליים==<br />
{{הערות שוליים|יישור=שמאל}}<br />
<br />
{{מחלקות סיבוכיות}}<br />
[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]<br />
[[קטגוריה:מחלקות סיבוכיות]]<br />
[[קטגוריה:בעיות NP-קשות]]</div>imported>AutoMod