PPAD

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

הגדרת הבעיה

יהי $G(V,E)$ גרף מכוון. נאמר ש-$v\in V$ הוא צומת לא מאוזן אם מספר הקשתות הנכנסות שונה ממספר הקשתות היוצאות. טיעון הזוגיות מראה כי בגרף מסוג זה מספר הצמתים הלא-מאוזנים הוא זוגי. בעיית החיפוש המתאימה מקבלת גרף מכוון $G$ וצומת לא-מאוזן $v$ ומחזירה צומת לא מאוזן $v'$ כך ש-$v\neq v'$.

לקריאה נוספת

• The Complexity of Computing a Nash Equilibrium. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou,
• Algorithmic Game Theory. Edited by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Cambridge University Press

קישורים חיצוניים

• "A Compendium of PPAD-complete problems". אורכב מ-המקור ב-2013-01-03. נבדק ב-2012-12-28.
• "Computational Complexity, What is PPAD?".
• "Introduction to PPAD".
• "Christos Papadimitriou's home page".