TFNP

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת הסיבוכיות, TFNP‏ (Total Function Nondeterministic Polynomial) היא מחלקת סיבוכיות המהווה תת-מחלקה של מחלקת הסיבוכיות FNP בה מובטח כי קיים פתרון.

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

המחלקות PPA, PLS, FP ו-PPAD הן תת-מחלקות של TFNP הנבדלות ביניהן בשיטת ההוכחה בה משתמשים כדי להוכיח קיום של פתרון.

לקריאה נוספת[עריכת קוד מקור | עריכה]