PPAD
Em ciência da computação, PPAD ("Polinômio de Paridade de Argumentos em Grafos Direcionados") é uma classe de complexidade introduzida por Christos Papadimitriou, em 1994. PPAD é uma subclasse da TFNP com base nas funções que podem ser mostradas serem totais, por um argumento de paridade.[1][2] A classe atraiu atenção significativa no campo da teoria dos jogos algorítmica, porque ele contém o problema de cálculo de um equilíbrio de Nash, e este problema foi apresentado por Chen e Deng, em 2005, como completo para a classe.[3]
PPAD é uma classe de problemas que se acredita ser difícil, mas a obtenção de PPAD-completude é uma evidência mais fraca na prova de intratabilidade do que a obtenção de NP-completude. Problemas PPAD não podem ser NP-completos, pela razão técnica que NP é uma classe de problemas de decisão, mas a resposta de problemas PPAD é sempre sim, visto que é sabido que um solução existe, embora possa ser difícil encontrar a solução.[4] Ainda poderia ser o caso que PPAD é a mesma classe que P, e ainda teriamos que , porém isso parece improvável. Exemplos de Problemas PPAD-completos incluem encontrar equilíbrios de Nash, computar pontos fixos em funções de Brouwer, encontrar equilíbrios de Arrow-Debreu em mercados e muito mais.[5]
Definição[editar | editar código-fonte]
PPAD é um subconjunto da classe TFNP, a classe de problemas de função em FNP que são garantidas serem totais. A definição formal de TFNP é dada da seguinte forma:
- Uma relação binária P(x,y) está em TFNP se, e somente se, existe um algoritmo determinístico de tempo polinomial que pode determinar se P(x,y) se verifica dados ambos x e y, e para cada x existe um y tal que P(x,y), se verifica.
Subclasses de TFNP são definidas com base no tipo de prova matemática usada para provar que uma solução sempre existe. Informalmente, PPAD é a subclasse de TFNP, onde a garantia de que existe um y tal que P(x,y) é baseada em um argumento de paridade em um grafo direcionado. A classe é formalmente definida especificando-se um de seus problemas completos, conhecido como Fim Da Linha:
- G é um (possivelmente exponencialmente grande) grafo direcionado sem qualquer vértice isolado, e com cada vértice tendo no máximo um antecessor e um sucessor. G é especificado dando-se uma função computável em tempo polinomial f(v) (polinomial no tamanho de v) que retorna o antecessor e o sucessor (se existirem) do vértice v. Dado um vértice s de G com nenhum antecessor, encontre um vértice t≠s com nenhum antecessor ou nenhum sucessor. (A entrada para o problema é vértice de origem s e a função f(v)). Em outras palavras, queremos fonte e destino de qualquer grafo direcionado que não seja s.
Tal t deve existir se um s existe, porque a estrutura de G significa que os vértices com apenas um vizinho vem em pares. Em particular, dado s, podemos encontrar um t na outra ponta da cadeia começando em s. (Observe que isso pode levar um tempo exponencial, se apenas calcularmos f repetidamente.)
Relação com outras classes de complexidade[editar | editar código-fonte]
PPAD está contido na (mas não se sabe se igual a) PPA (classe correspondente a paridade de argumentos para grafos não direcionados) que está contido em TFNP. PPAD também está contido na (mas não se sabe se igual a) PPP, outra subclasse da TFNP. Ele contém CLS.[6]
Outros problemas completos notáveis[editar | editar código-fonte]
- Encontrar o equilíbrio de Nash em um jogo com 2 jogadores[3] ou um jogo com qualquer número de jogadores.[5]
- Encontrar um ponto tri-colorido no Lema de Sperner.[7]
- Encontrar um corte de bolo livre de inveja quando as funções de utilidade são dadas por algoritmos de tempo polinomial.[8]
References[editar | editar código-fonte]
- ↑ Christos Papadimitriou (1994). «On the complexity of the parity argument and other inefficient proofs of existence» (PDF). Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016/S0022-0000(05)80063-7
- ↑ Fortnow, Lance (2005). «What is PPAD?». Consultado em 29 de janeiro de 2007
- ↑ a b Chen, Xi; Deng, Xiaotie (2006). Settling the complexity of two-player Nash equilibrium. Proc. 47th Symp. Foundations of Computer Science. pp. 261–271. doi:10.1109/FOCS.2006.69. Predefinição:ECCC.
- ↑ Scott Aaronson (2011). «Why philosophers should care about computational complexity». arXiv:1108.1791
- ↑ a b 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. doi:10.1137/070699652
- ↑ Daskalakis, C.; Papadimitriou, C. (23 de janeiro de 2011). Continuous Local Search. Col: Proceedings. [S.l.]: Society for Industrial and Applied Mathematics. pp. 790–804. ISBN 9780898719932. doi:10.1137/1.9781611973082.62
- ↑ Xi Chen and Xiaotie Deng (2006). «On the Complexity of 2D Discrete Fixed Point Problem». International Colloquium on Automata, Languages and Programming. pp. 489–500. Predefinição:ECCC
- ↑ Deng, X.; Qi, Q.; Saberi, A. (2012). «Algorithmic Solutions for Envy-Free Cake Cutting». Operations Research. 60 (6). 1461 páginas. doi:10.1287/opre.1120.1116
Ligações externas[editar | editar código-fonte]
- Shiva Kintali. «A Compendium of PPAD-complete problems». Consultado em 8 de julho de 2016. Arquivado do original em 3 de janeiro de 2013"Um Compêndio de PPAD-completa problemas".