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

ראו גם[עריכת קוד מקור | עריכה]

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

מקורות[עריכת קוד מקור | עריכה]

  • Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, ISBN 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.