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