FNP

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

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

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

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

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

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

מקורות

• Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, מסת"ב 0-13-228806-0, 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 בה מובטח כי קיים פתרון.

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

FNP38516155Q2898287