כל מה שרצית לדעת על FNP:
בתורת הסיבוכיות, מחלקת הסיבוכיות FNP היא ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה NP.
בעיות רבות ב-NP, ובהן גם מספר רב של בעיות NP-שלמות, שואלות מתי חפץ מסוים קיים, כמו השמה מספקת, צביעת גרף, או מציאת קליקה בגודל מסוים.
גרסות ה-FNP עבור בעיות אלה, שואלות לא רק האם קיים פתרון אלא גם מהו אותו פתרון.
הגדרה פורמלית:יחס בינארי   P ( x , y ) {\displaystyle \ P(x,y)} , שבו | y | {\displaystyle |y|} לכל היותר גדול פולינומית מ- | x | {\displaystyle |x|} , הוא ב-FNP אם ורק אם יש אלגוריתם דטרמיניסטי עם זמן ריצה פולינומי באורך הקלט שיכול להכריע האם   P ( x , y ) {\displaystyle \ P(x,y)} מתקיים בהינתן x {\displaystyle x} ו- y {\displaystyle y} .
ההגדרה אינה כוללת אי-דטרמיניזם והיא אנלוגית להגדרת המוודא של NP.
קיימת שפה ב-NP המתאימה לכל יחס ב-FNP באופן ישיר, שלעיתים נקראת בעיית הכרעת FNP.
זו השפה הנוצרת על ידי לקיחת כל ה- x {\displaystyle x} ים עבורם   P ( x , y ) {\displaystyle \ P(x,y)} מתקיים עבור y {\displaystyle y} מסוים.
למרות זאת, יכול להיות יותר מיחס FNP אחד עבור בעיית הכרעה כלשהי ב-NP.
דוגמה ליחס ב-FNP הוא היחס P ( x , y ) {\displaystyle P(x,y)} שמתקיים כאשר y {\displaystyle y} הוא פירוק לגורמים של x {\displaystyle x} (אליו מתייחסים כמספר שלם).
לבעיה זו לא ידוע אלגוריתם פולינומי וקושי החישוב המשוער שלה הוא הבסיס למספר שיטות הצפנה א-סימטרית.
כל בעיה NP-שלמה ניתנת לרדוקציה עצמית (למשל דרך הרדוקציה העצמית של בעיית ההשמה המספקת) ולכן גרסת ה-FNP שלה לא יותר קשה מבעיית ההכרעה.
לעומת זאת, מיהיר בלר ושפי גולדווסר הראו ב-1991, על סמך מספר הנחות סטנדרטיות, שקיימות שפות ב-NP כך שכל גרסות ה-FNP שלהן אינן ניתנות לרדוקציה עצמית, עובדה הרומזת על כך שבעיית ההכרעה קלה יותר מכל בעיות החיפוש המתאימות לה.

נלקח מויקיפדיה

הגדרות נוספות הקשורות לFNP:
•מחלקות סיבוכיות