PPAD 완료 문제 목록
List of PPAD-complete problems이것은 PPAD-완전한 문제의 목록이다.
고정 점 정리
게임 이론
게임 이론과 경제학의 평형성
- 피셔 시장 평형률
- 애로우 데브레우 에클리브리아
- 동일 소득에서 얻는 대략적인 경쟁적 균형
- 금융 네트워크에서 결제 정보 찾기
그래프 이론
- 안정적 소수 경로 문제
- 부분 하이퍼그래프 일치(NP 완료 하이퍼그래프 일치 참조)
- 분수 스트롱 커널
잡다한
참조
- Papadimitriou, Christos (1994). "On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence". Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016/S0022-0000(05)80063-7. 파파디미트리오 홈페이지에서 온라인으로 볼 수 있는 종이.
- C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou (2009). "The Complexity of Computing a Nash Equilibrium". SIAM Journal on Computing. 39 (3): 195–259. CiteSeerX 10.1.1.68.6111. doi:10.1137/070699652.
- Xi Chen and Xiaotie Deng (2006). "Settling the complexity of two-player Nash equilibrium". In Proc. 47th FOCS. pp. 261–272.
