FNP

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-colors-edit-find-replace.svg יש לשכתב ערך זה. ייתכן שהערך מכיל טעויות, או שהניסוח וצורת הכתיבה שלו אינם מתאימים.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

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

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

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

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

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

FNP=FP אם ורק אם P=NP.

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

  • 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.