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

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