b'\n_START_ARTICLE_\nPPAD\n_START_PARAGRAPH_\nEm ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o, PPAD ("Polin\xc3\xb4mio de Paridade de Argumentos em Grafos Direcionados") \xc3\xa9 uma classe de complexidade introduzida por Christos Papadimitriou, em 1994. PPAD \xc3\xa9 uma subclasse da TFNP com base nas fun\xc3\xa7\xc3\xb5es que podem ser mostradas serem totais, por um argumento de paridade. A classe atraiu aten\xc3\xa7\xc3\xa3o significativa no campo da teoria dos jogos algor\xc3\xadtmica, porque ele cont\xc3\xa9m o problema de c\xc3\xa1lculo de um equil\xc3\xadbrio de Nash, e este problema foi apresentado por Chen e Deng, em 2005, como completo para a classe._NEWLINE_PPAD \xc3\xa9 uma classe de problemas que se acredita ser dif\xc3\xadcil, mas a obten\xc3\xa7\xc3\xa3o de PPAD-completude \xc3\xa9 uma evid\xc3\xaancia mais fraca na \xc2\xa0prova de intratabilidade do que a obten\xc3\xa7\xc3\xa3o de NP-completude. Problemas\xc2\xa0PPAD n\xc3\xa3o podem ser NP-completos, pela raz\xc3\xa3o t\xc3\xa9cnica que NP \xc3\xa9 uma classe de problemas de decis\xc3\xa3o, mas a resposta de problemas PPAD \xc3\xa9 sempre sim, visto que \xc3\xa9 sabido que um solu\xc3\xa7\xc3\xa3o existe, embora possa ser dif\xc3\xadcil encontrar a solu\xc3\xa7\xc3\xa3o. Ainda poderia ser o caso que PPAD \xc3\xa9 a mesma classe que P, e ainda teriamos que , por\xc3\xa9m isso parece improv\xc3\xa1vel. Exemplos de Problemas PPAD-completos incluem encontrar equil\xc3\xadbrios de Nash, computar pontos fixos em fun\xc3\xa7\xc3\xb5es\xc2\xa0de Brouwer, encontrar\xc2\xa0equil\xc3\xadbrios de Arrow-Debreu em mercados e muito mais.\n_START_SECTION_\nRela\xc3\xa7\xc3\xa3o com outras classes de complexidade\n_START_PARAGRAPH_\nPPAD est\xc3\xa1 contido na (mas n\xc3\xa3o se sabe se igual a)\xc2\xa0PPA (classe correspondente a paridade de argumentos para grafos n\xc3\xa3o direcionados) que est\xc3\xa1 contido em TFNP. PPAD tamb\xc3\xa9m est\xc3\xa1 contido na (mas n\xc3\xa3o se sabe se igual a) PPP, outra subclasse da TFNP. Ele cont\xc3\xa9m CLS.'