In computer science, PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium: this problem was shown to be complete for PPAD by Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - PPAD (complexité) (fr)
- PPAD (complexity) (en)
- PPAD (pt)
|
| rdfs:comment
| - En informatique théorique, PPAD (Polynomial Parity Arguments on Directed graphs) est une classe de complexité introduite par Christos Papadimitriou en 1994. Cette classe est importante en théorie des jeux algorithmique car elle contient le problème de calculer un équilibre de Nash et ce problème a été démontré PPAD-complet par Chen et Deng en 2005. (fr)
- In computer science, PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium: this problem was shown to be complete for PPAD by Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players. (en)
- 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 , 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. (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En informatique théorique, PPAD (Polynomial Parity Arguments on Directed graphs) est une classe de complexité introduite par Christos Papadimitriou en 1994. Cette classe est importante en théorie des jeux algorithmique car elle contient le problème de calculer un équilibre de Nash et ce problème a été démontré PPAD-complet par Chen et Deng en 2005. (fr)
- In computer science, PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium: this problem was shown to be complete for PPAD by Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players. (en)
- 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 , 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 , 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 em mercados e muito mais. (pt)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)