FNP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
טוסברהינדי (שיחה | תרומות) מ קישורים פנימיים |
מי האידיוט שכתב את מה שהיה כתוב פה לפני העריכה?! |
||
שורה 8:
בעיות רבות ב-NP, ובהן גם מספר רב של [[בעיה NP-שלמה|בעיות NP-שלמות]], שואלות מתי חפץ מסוים קיים, כמו השמה מספקת, [[צביעת גרף]], או מציאת [[קליקה (תורת הגרפים)|קליקה]] בגודל מסוים. גרסות ה-FNP עבור בעיות אלה, שואלות לא רק האם קיים פתרון אלא גם מהו ערכו. כלומר, גרסת ה-FNP של כל בעיה NP-שלמה היא [[בעיה NP-קשה|NP-קשה]].
בלר ו[[שפי גולדווסר|גולדווסר]] הראו ב-1991, דרך שימוש בכמה הנחות סטנדרטיות, שקיימות בעיות
FNP=FP [[אם ורק אם]] [[P=NP]].
| |||