FNP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 4:
[[יחס בינארי]] <math>\ P(x,y)</math>, שבו <math>|y|</math> לכל היותר גדול פולינומית מ-<math>|x|</math>, הוא ב-FNP [[אם ורק אם]] יש [[אלגוריתם דטרמיניסטי]] עם [[סיבוכיות זמן|זמן ריצה פולינומי]] שיכול להכריע האם <math>\ P(x,y)</math> מתקיים בהינתן <math>x</math> ו-<math>y</math>.
ההגדרה אינה כוללת [[מכונת טיורינג לא-דטרמיניסטית|אי-דטרמיניזם]] והיא אנלוגית להגדרת המוודא של NP. קיימת שפה ב-NP המתאימה לכל יחס ב-FNP באופן ישיר, שלעתים נקראת בעיית הכרעת FNP. זו השפה הנוצרת על ידי לקיחת כל ה-xים עבורם <math>\ P(x,y)</math> מתקיים עבור
בעיות רבות ב-NP, ובהן גם מספר רב של [[בעיה NP-שלמה|בעיות NP-שלמות]], שואלות מתי חפץ מסוים קיים, כמו [[בעיית הספיקות|השמה מספקת]], [[צביעת גרף]], או מציאת [[גרף שלם|קליקה]] בגודל מסוים. גרסות ה-FNP עבור בעיות אלה, שואלות לא רק האם קיים פתרון אלא גם מהו אותו פתרון
כל בעיה NP-שלמה ניתנת ל[[רדוקציה עצמית]]
FNP=FP [[אם ורק אם]] [[P=NP]].
== מקורות ==
| |||