TFNP – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־13:57, 6 בנובמבר 2016

בתורת הסיבוכיות, 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).

@@ שורה 1: / שורה 1: @@
 ב[[תורת הסיבוכיות]], '''TFNP'''{{כ}} (Total Function Nondeterministic Polynomial) היא [[מחלקת סיבוכיות]] המהווה תת-מחלקה של מחלקת הסיבוכיות [[FNP]] בה מובטח כי קיים פתרון.
-[[יחס בינארי]] <math> \ P(x,y)</math> הוא ב-FTNP [[אם ורק אם]] קיים [[אלגוריתם דטרמיניסטי]] בעל [[סיבוכיות זמן|זמן ריצה פולינומי]] היכול לזהות, בהינתן x ו-y האם האם <math>\ P(x,y)=1</math> (כלומר, היחס הוא ב-[[FNP]]), ולכל x מובטח כי קיים y כך שהזוג הסדור (x,y) מקיים <math>(x,y) \in P</math>. [[אלגוריתם]] נקרא אלגוריתם TFNP אם בהינתן [[קלט]] x, האלגוריתם מוצא [[פלט]] y אחד בדיוק כך ש-<math> \ P(x,y)=1 </math>.
+[[יחס בינארי]] <math> \ P(x,y)</math> הוא ב-FTNP [[אם ורק אם]] קיים [[אלגוריתם דטרמיניסטי]] בעל [[סיבוכיות זמן|זמן ריצה פולינומי]] היכול לזהות, בהינתן x ו-y האם האם <math>\ P(x,y)=1</math> (כלומר, היחס הוא ב-[[FNP]]), ולכל x מובטח כי קיים y כך שהזוג הסדור (x,y) מקיים <math>(x,y) \in P</math>.
 המחלקות [[PPA (סיבוכיות)|PPA]], [[PPP (מחלקת סיבוכיות)|PPP]] ,PLS, [[FP]] ו-[[PPAD]] הן תת-מחלקות של TFNP הנבדלות ביניהן בשיטת ה[[הוכחה]] בה משתמשים כדי להוכיח קיום של פתרון. כך, למשל, PPP ("Polynomial Pigeonhole Principle") מוגדרת על ידי הבעיות בהן קיום פתרון מובטח על ידי [[עקרון שובך היונים]].