FP
בתורת הסיבוכיות, מחלקת הסיבוכיות FP היא ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה P, כלומר אוסף בעיות הפונקציה שאפשר לחשב בזמן ריצה פולינומי על ידי מכונת טיורינג דטרמיניסטית. בעיות רבות ב-P מנוסחות בצורת שאלה, מתי רכיב מסוים קיים, כמו בהינתן גרף האם יש בו שידוך מושלם. גרסת ה-FP עבור בעיות אלה, שואלת לא רק האם קיים פתרון אלא גם מהו אותו פתרון, כלומר בדוגמת הגרף הבעיה היא למצוא שידוך מושלם.
באופו פורמלי יותר יחס בינארי $ \ P(x,y) $ הוא ב-FP אם ורק אם יש אלגוריתם דטרמיניסטי עם זמן ריצה פולינומי ב-$ |x| $ שיכול בהינתן $ x $ למצוא $ y $ כך שמתקיים $ \ P(x,y) $ אם קיים $ y $ כזה. בדוגמה של השידוך המושלם היחס מתקיים כש$ x $ הוא גרף ו-$ y $ הוא שידוך מושלם בגרף. יחס זה הוא ב-FP כי ידוע אלגוריתם פולינומי למציאת השידוך.
המחלקה עולה במחקר בסיבוכיות בהקשר של מחלקת FNP ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה NP. ידוע ש FNP=FP אם ורק אם P=NP. שאלה נוספת העולה היא הכח של FP לעומת FL, מחלקת הפונקציות אותן ניתן לחשב על ידי מכונת טיורינג דטרמיניסטית אשר משתמשת בזיכרון שגודלו לוגריתמי בגודל הקלט.
שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] FP19543680