FNP

בתורת הסיבוכיות, מחלקת הסיבוכיות FNP היא ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה NP. בעיות רבות ב-NP, ובהן גם מספר רב של בעיות NP-שלמות, שואלות מתי חפץ מסוים קיים, כמו השמה מספקת, צביעת גרף, או מציאת קליקה בגודל מסוים. גרסות ה-FNP עבור בעיות אלה, שואלות לא רק האם קיים פתרון אלא גם מהו אותו פתרון. 

הגדרה פורמלית:

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

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

דוגמה ליחס ב-FNP הוא היחס  שמתקיים כאשר  הוא פירוק לגורמים  של  (אליו מתייחסים כמספר שלם). לבעיה זו לא ידוע אלגוריתם פולינומי וקושי החישוב המשוער שלה הוא הבסיס למספר שיטות הצפנה א-סימטרית.

כל בעיה NP-שלמה ניתנת לרדוקציה עצמית (למשל דרך הרדוקציה העצמית של בעיית ההשמה המספקת) ולכן גרסת ה-FNP שלה לא יותר קשה מבעיית ההכרעה. לעומת זאת, מיהיר בלר ושפי גולדווסר הראו ב-1991, על סמך מספר הנחות סטנדרטיות, שקיימות שפות ב-NP כך שכל גרסות ה-FNP שלהן אינן ניתנות לרדוקציה עצמית, עובדה הרומזת על כך שבעיית ההכרעה קלה יותר מכל בעיות החיפוש המתאימות לה.

 מקורות 
 Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, , section 28.10 "The problem classes FP and FNP", pp. 689-694
 M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM Journal on Computing, Vol. 23, No. 1, February 1994.

ראו גם
 FP מחלקת הפונקציות אותן ניתן לחשב בזמן פולינומי. FNP=FP אם ורק אם P=NP.
 TFNP תת-מחלקה של FNP בה מובטח כי קיים פתרון.

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