TFNP

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

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

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

לקריאה נוספת

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