TFNP: הבדלים בין גרסאות

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

עריכות