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 בה מובטח כי קיים פתרון.
FNP38516155Q2898287