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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

19543680FP