הבדלים בין גרסאות בדף "PPAD"

נוספו 35 בתים ,  לפני 4 שנים
אין תקציר עריכה
מ (שינוי סדר פרקים לפי ויקיפדיה:פרלמנט/ארכיון 40#הצבעה)
'''PPAD''' {{כ}}('''Polynomial Parity Arguments on Directed graphs''') היא [[מחלקת סיבוכיות]] המהווה תת-מחלקה של מחלקת הסיבוכיות [[TFNP]]. [[יחס בינארי]] שייך ל-PPAD אם ניתן להראות שהוא שייך ל-TFNP באמצעות הוכחה על [[דרגה (תורת הגרפים)|דרגות]] הצמתים ב[[גרף מכוון]]. המחלקה הוצגה לראשונה על ידי פרופסור [[קריסטוס פאפאדימיטריו]] מ[[אוניברסיטת ברקלי]] בשנת [[1994]]. חשיבותה של המחלקה נובעת מכך שניתן להראות שבעיית חישוב [[שיווי משקל נאש]] (אפילו לשני שחקנים) שלמה תחת מחלקה זו.
 
== הגדרת הבעיה ==
1,197

עריכות