Mostrar código-fonte de 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.<ref>{{Citar periódico|author=[[Christos Papadimitriou]]|year=1994|title=On the complexity of the parity argument and other inefficient proofs of existence|journal=Journal of Computer and System Sciences|volume=48|issue=3|pages=498–532|url=http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf|doi=10.1016/S0022-0000(05)80063-7}}</ref><ref>{{Citar web|first=Lance|last=Fortnow|authorlink=Lance Fortnow|year=2005|title=What is PPAD?|url=http://weblog.fortnow.com/2005/12/what-is-ppad.html|accessdate=2007-01-29}}</ref> A classe atraiu atenção significativa no campo da [[teoria algorítmica dos jogos|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.<ref name="chen2005">{{Citar conferência|first1=Xi|last1=Chen|first2=Xiaotie|last2=Deng|title=Settling the complexity of two-player Nash equilibrium|conference=Proc. 47th Symp. Foundations of Computer Science|year=2006|pages=261–271|doi=10.1109/FOCS.2006.69|id={{ECCC|2005|05|140}}|postscript=<!--None-->}}.</ref>

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-completo|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.<ref>{{Citar arXiv|author=[[Scott Aaronson]]|year=2011|title=Why philosophers should care about computational complexity|arxiv=1108.1791}}</ref> Ainda poderia ser o caso que PPAD é a mesma classe que [[P (complexidade)|P]], e ainda teriamos que <math>P\neq NP</math>, porém isso parece improvável. Exemplos de Problemas PPAD-completos incluem encontrar [[Equilíbrio de Nash|equilíbrios de Nash]], computar pontos fixos em funções de [[Teorema do ponto fixo de Brouwer|Brouwer]], encontrar [[equilíbrios de Arrow-Debreu]] em mercados e muito mais.<ref name="Daskalakis2009">{{Citar periódico|doi=10.1137/070699652|author=C. Daskalakis, P.W. Goldberg and [[Christos Papadimitriou|C.H. Papadimitriou]]|year=2009|title=The Complexity of Computing a Nash Equilibrium|journal=[[SICOMP|SIAM Journal on Computing]]|volume=39|issue=3|pages=195–259}}</ref>

== Definição ==
PPAD é um [[subconjunto]] da classe [[TFNP]], a classe de [[Problema de função|problemas de função]] em FNP que são garantidas serem [[Função parcial|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 (teoria dos grafos)|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&#x2260;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 ==
PPAD está contido na (mas não se sabe se igual a) [[PPA (complexidade)|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 [http://people.csail.mit.edu/costis/CLS.pdf CLS].<ref>{{Citar livro|url=http://epubs.siam.org/doi/abs/10.1137/1.9781611973082.62|title=Continuous Local Search|last=Daskalakis|first=C.|last2=Papadimitriou|first2=C.|date=2011-01-23|publisher=Society for Industrial and Applied Mathematics|isbn=9780898719932|series=Proceedings|pages=790–804|doi=10.1137/1.9781611973082.62}}</ref>

== Outros problemas completos notáveis ==
* Encontrar o [[equilíbrio de Nash]] em um jogo com 2 jogadores<ref name="chen2005">{{Citar conferência|first1=Xi|last1=Chen|first2=Xiaotie|last2=Deng|title=Settling the complexity of two-player Nash equilibrium|conference=Proc. 47th Symp. Foundations of Computer Science|year=2006|pages=261–271|doi=10.1109/FOCS.2006.69|id={{ECCC|2005|05|140}}|postscript=<!--None-->}}.</ref> ou um jogo com qualquer número de jogadores.<ref name="Daskalakis2009">{{Citar periódico|doi=10.1137/070699652|author=C. Daskalakis, P.W. Goldberg and [[Christos Papadimitriou|C.H. Papadimitriou]]|year=2009|title=The Complexity of Computing a Nash Equilibrium|journal=[[SICOMP|SIAM Journal on Computing]]|volume=39|issue=3|pages=195–259}}</ref>

* Encontrar um ponto tri-colorido no [[Lema de Sperner]].<ref>{{Citar conferência|author=Xi Chen and Xiaotie Deng|title=On the Complexity of 2D Discrete Fixed Point Problem|booktitle=International Colloquium on Automata, Languages and Programming|year=2006|pages=489–500|id={{ECCC|2006|06|037}}}}</ref>
* Encontrar um [[corte de bolo livre de inveja]] quando as funções de utilidade são dadas por algoritmos de tempo polinomial.<ref>{{Citar periódico|doi=10.1287/opre.1120.1116|title=Algorithmic Solutions for Envy-Free Cake Cutting|journal=Operations Research|volume=60|issue=6|pages=1461|year=2012|last1=Deng|first1=X.|last2=Qi|first2=Q.|last3=Saberi|first3=A.}}</ref>

== References ==
{{Reflist}}

== Ligações externas ==
* {{Citar web|author=Shiva Kintali|title=A Compendium of PPAD-complete problems|url=http://www.cs.princeton.edu/~kintali/ppad.html|acessodata=2016-07-08|arquivourl=https://web.archive.org/web/20130103124641/http://www.cs.princeton.edu/~kintali/ppad.html|arquivodata=2013-01-03|urlmorta=yes}}<cite class="citation web">[https://web.archive.org/web/20130103124641/http://www.cs.princeton.edu/~kintali/ppad.html "Um Compêndio de PPAD-completa problemas"].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APPAD+%28complexity%29&rft.au=Shiva+Kintali&rft.btitle=A+Compendium+of+PPAD-complete+problems&rft.genre=unknown&rft_id=http%3A%2F%2Fwww.cs.princeton.edu%2F~kintali%2Fppad.html&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook">&#x20;</span>
[[Categoria:Classes de complexidade]]