PPAD (complexity) (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:wikiPageExternalLink | http://people.csail.mit.edu/costis/CLS.pdf |
| dbo:wikiPageID | 9192019 (xsd:integer) |
| dbo:wikiPageLength | 7452 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1106202859 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Nash_equilibrium dbr:Algorithmic_game_theory dbr:Christos_Papadimitriou dbr:Envy-free_cake-cutting dbr:Epsilon-equilibrium dbr:Complete_(complexity) dbr:Complexity_class dbr:Computer_science dbr:Function_problem dbr:PPA_(complexity) dbr:PPP_(complexity) dbr:Total_function dbr:TFNP dbr:Brouwer_fixed-point_theorem dbc:Complexity_classes dbr:Arrow–Debreu_model dbr:Nash_equilibria dbr:Vertex_(graph_theory) dbr:FNP_(complexity) dbr:FP_(complexity) dbr:Sperner's_Lemma dbr:NP-completeness dbr:P_versus_NP_problem |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Main dbt:Reflist |
| dct:subject | dbc:Complexity_classes |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| 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) |
| rdfs:label | PPAD (complexité) (fr) PPAD (complexity) (en) PPAD (pt) |
| owl:sameAs | freebase:PPAD (complexity) yago-res:PPAD (complexity) wikidata:PPAD (complexity) dbpedia-fr:PPAD (complexity) dbpedia-he:PPAD (complexity) dbpedia-pt:PPAD (complexity) https://global.dbpedia.org/id/4sr5j |
| prov:wasDerivedFrom | wikipedia-en:PPAD_(complexity)?oldid=1106202859&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:PPAD_(complexity) |
| is dbo:wikiPageRedirects of | dbr:PPAD dbr:PPAD-hard dbr:PPAD_complete |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Algorithmic_game_theory dbr:Indistinguishability_obfuscation dbr:PPA_(complexity) dbr:Succinct_game dbr:Carathéodory's_theorem_(convex_hull) dbr:Folk_theorem_(game_theory) dbr:List_of_PPAD-complete_problems dbr:Handshaking_lemma dbr:Economic_calculation_problem dbr:Sperner's_lemma dbr:End_of_the_Line dbr:Implicit_graph dbr:Fisher_market dbr:PPAD dbr:PPAD-hard dbr:PPAD_complete |
| is foaf:primaryTopic of | wikipedia-en:PPAD_(complexity) |