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

המחלקות PPA, PPP ,PLS, FP ו-PPAD הן תת-מחלקות של TFNP הנבדלות ביניהן בשיטת ההוכחה בה משתמשים כדי להוכיח קיום של פתרון. כך, למשל, PPP ("Polynomial Pigeonhole Principle") מוגדרת על ידי הבעיות בהן קיום פתרון מובטח על ידי עקרון שובך היונים.

העזרה לא יכולה לבוא משום גורם ללא עזרתך פניתי לכול הגורמים ברווחה כולל אתי כהן .אשמח אם אתה תעזור לי באופן אישי .יום שקט שיהייה לנו

לקריאה נוספת

• Megiddo and Papadimitriou, A Note on Total Functions, Existence Theorems and Computational Complexity (1989).