Matches in DBpedia 2014 for { <http://dbpedia.org/resource/PPAD_(complexity)> ?p ?o. }
Showing items 1 to 19 of
19
with 100 items per page.
- PPAD_(complexity) abstract "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, and this problem was shown by Chen and Deng in 2005 to be complete for the class.PPAD is a class of problems that are believed to be hard, but obtaining PPAD-completeness is a weaker evidence of intractability than that of obtaining NP-completeness. It could still be the case that PPAD is the same class as P, and still have that P NP, though it seems unlikely. Examples of PPAD-complete problems include finding Nash equilibria, Brouwer and Borsuk-Ulam fixpoints, finding Arrow-Debreu equilibria in markets and more (The Complexity of Finding Nash Equilibria, Papadimitriou). The Ham sandwich theorem is known to lie in PPAD but it remains an open question as to whether or not it is PPAD-complete.".
- PPAD_(complexity) wikiPageExternalLink ppad.html.
- PPAD_(complexity) wikiPageID "9192019".
- PPAD_(complexity) wikiPageRevisionID "580204353".
- PPAD_(complexity) hasPhotoCollection PPAD_(complexity).
- PPAD_(complexity) subject Category:Complexity_classes.
- PPAD_(complexity) type Abstraction100002137.
- PPAD_(complexity) type Class107997703.
- PPAD_(complexity) type Collection107951464.
- PPAD_(complexity) type ComplexityClasses.
- PPAD_(complexity) type Group100031264.
- PPAD_(complexity) comment "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.".
- PPAD_(complexity) label "PPAD (complexity)".
- PPAD_(complexity) sameAs m.027_s7d.
- PPAD_(complexity) sameAs Q7120085.
- PPAD_(complexity) sameAs Q7120085.
- PPAD_(complexity) sameAs PPAD_(complexity).
- PPAD_(complexity) wasDerivedFrom PPAD_(complexity)?oldid=580204353.
- PPAD_(complexity) isPrimaryTopicOf PPAD_(complexity).