FP

בתורת הסיבוכיות, מחלקת הסיבוכיות FP היא ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה P, כלומר אוסף בעיות הפונקציה שאפשר לחשב בזמן ריצה פולינומי על ידי מכונת טיורינג דטרמיניסטית. בעיות רבות ב-P מנוסחות בצורת שאלה, מתי רכיב מסוים קיים, כמו בהינתן גרף האם יש בו שידוך מושלם. גרסת ה-FP עבור בעיות אלה, שואלת לא רק האם קיים פתרון אלא גם מהו אותו פתרון, כלומר בדוגמת הגרף הבעיה היא למצוא שידוך מושלם. 

באופו פורמלי יותר  יחס בינארי  הוא ב-FP אם ורק אם יש אלגוריתם דטרמיניסטי עם זמן ריצה פולינומי ב- שיכול בהינתן  למצוא  כך שמתקיים  אם קיים  כזה. בדוגמה של השידוך המושלם היחס מתקיים כש הוא גרף ו- הוא שידוך מושלם בגרף. יחס זה הוא ב-FP כי ידוע אלגוריתם פולינומי למציאת השידוך.

המחלקה עולה במחקר בסיבוכיות בהקשר של מחלקת FNP ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה NP. ידוע ש FNP=FP אם ורק אם P=NP. שאלה נוספת העולה היא הכח של FP לעומת FL, מחלקת הפונקציות אותן ניתן לחשב על ידי מכונת טיורינג דטרמיניסטית אשר משתמשת בזיכרון שגודלו לוגריתמי בגודל הקלט. 

קטגוריה:מחלקות סיבוכיות