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, מחלקת הפונקציות אותן ניתן לחשב על ידי מכונת טיורינג דטרמיניסטית אשר משתמשת בזיכרון שגודלו לוגריתמי בגודל הקלט.