Seznam úplných problémů s PPAD - List of PPAD-complete problems

Toto je seznam PPAD -kompletní problémy.

Věty o pevném bodě

• Spernerovo lemma
• Brouwerova věta o pevném bodě
• Kakutaniho věta o pevném bodě

Herní teorie

• Nashova rovnováha
• Jádro vyvážených her

Rovnováha v teorii a ekonomii her

• Rovnováhy na trhu Fisher
• Arrow-Debreu Equilibria
• Přibližná konkurenční rovnováha ze stejných příjmů
• Hledání zúčtování plateb ve finančních sítích

Teorie grafů

• Problémy se zlomkovými stabilními cestami
• Frakční shoda hypergrafu (viz také NP-kompletní Shoda hypergrafu )
• Frakční silné jádro

Smíšený

• Šála Lemma
• Frakční hry s omezeným rozpočtovým připojením

Reference

• Papadimitriou, Christos (1994). „O složitosti argumentu parity a dalších neúčinných důkazech existence“. Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016 / S0022-0000 (05) 80063-7. Papír je k dispozici online na adrese Domovská stránka společnosti Papadimitriou.

• C. Daskalakis, P.W. Goldberg a C.H. Papadimitriou (2009). "Složitost výpočtu Nashovy rovnováhy". SIAM Journal on Computing. 39 (3): 195–259. CiteSeerX  10.1.1.68.6111. doi:10.1137/070699652.

• Xi Chen a Xiaotie Deng (2006). Vyřešení složitosti Nashovy rovnováhy pro dva hráče. 261–272.