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. 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.

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. Ainda poderia ser o caso que PPAD é a mesma classe que P, e ainda teriamos que formula_1, 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.
Q21198
ciência da computação
Concept
Q908207
classe de complexidade
Concept
Q92639
Christos Papadimitriou
PER
Q2898181
TFNP
MISC
None
teoria dos jogos algorítmica
UNK
Q23389
equilíbrio de Nash
Concept
Q215206
NP-completude
MISC
Q846354
P
MISC
Q23389
equilíbrios de Nash
Concept
Q1144897
Brouwer
MISC
None
equilíbrios de Arrow-Debreu
UNK
Q7120085
PPAD
MISC
Q7120085
PPAD
MISC
Q7120085
PPAD
MISC
Q7120085
PPAD
MISC
Q7120085
PPAD
MISC
Q7120085
PPAD
MISC
Q7120085
PPAD
MISC
Q7120085
PPAD
MISC
+1994^^http://www.w3.org/2001/XMLSchema#decimal
1994
NUMBER
+2005^^http://www.w3.org/2001/XMLSchema#decimal
2005
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
instance of
field of work