TFNP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 3:
[[יחס בינארי]] <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>.
המחלקות [[PPA (סיבוכיות)|PPA]], [[PPP (מחלקת סיבוכיות)|PPP]] ,PLS, [[FP]] ו-[[PPAD]] הן תת-מחלקות של TFNP הנבדלות ביניהן בשיטת ה[[הוכחה]] בה משתמשים כדי להוכיח קיום של פתרון. כך, למשל, PPP ("Polynomial Pigeonhole Principle") מוגדרת על ידי הבעיות בהן קיום פתרון מובטח על ידי [[עקרון שובך היונים]].
== לקריאה נוספת ==
| |||