tag:blogger.com,1999:blog-3722233.post112966322183791986..comments2024-08-14T11:02:25.667-05:00Comments on Computational Complexity: Finding Nash has Same Complexity as Finding Fixed PointsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-1142009087037722342006-03-10T10:44:00.000-06:002006-03-10T10:44:00.000-06:00"Can someone comment on the relation between PPAD ..."Can someone comment on the relation between PPAD and NP? Does a polytime algorithm for one imply a polytime algorithm for the other?"<BR/><BR/>Polynomial algorithm for NP implies polynomial one for TFNP (and PPAD in particular). The proof is easy - you can iteratively ask the hypothetical NP algorithm for consecutive bits of the solution for the TFNP problem.<BR/>The other implication is unproven. In particular, proving a TFNP problem to be NP-hard would imply NP=co-NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134198735927900832005-12-10T01:12:00.000-06:002005-12-10T01:12:00.000-06:00Oops, forgot the link: ftp://ftp.eccc.uni-trier.de...Oops, forgot the link:<BR/><BR/> ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2005/TR05-140/Paper.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134198699102695032005-12-10T01:11:00.000-06:002005-12-10T01:11:00.000-06:00Here's a link to the paper about 2-Nash being PPAD...Here's a link to the paper about 2-Nash being PPAD-complete. Papadimitriou mentioned it in his invited talk at the NIPS conference, along with the clever comment "Game Over." :-)<BR/><BR/>Can someone comment on the relation between PPAD and NP? Does a polytime algorithm for one imply a polytime algorithm for the other?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134038831881894522005-12-08T04:47:00.000-06:002005-12-08T04:47:00.000-06:00I know the results on PPAD-Completeness of >=3 pla...I know the results on PPAD-Completeness of >=3 player games. But is this also true for 2 player games? Is there a reference for this?<BR/><BR/>Thanx in advance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133779599875745172005-12-05T04:46:00.000-06:002005-12-05T04:46:00.000-06:00Well, it appears that now both the 2- and 3-player...Well, it appears that now both the 2- and 3-player cases are solved; both are PPAD-complete.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130019828614379482005-10-22T17:23:00.000-05:002005-10-22T17:23:00.000-05:00As a co-author of the paper (as well as a reader o...As a co-author of the paper (as well as a reader of this blog), let me thank Lance for taking the trouble to bring it to the attention of other readers! Anonymous wrote:<BR/><BR/><I>Do you know of a good overview reference [for PPAD/TFNP], or at least one or two papers that cover the important aspects in some clarity?</I><BR/><BR/>I recommend Papadimitriou's 1994 JCSS paper that is cited in the Nash/PPAD paper. The definitions start in Section 2; you may wish to skip Section 1 to begin with. I must admit, when I read it, I was in the happy position of being able to quiz the author on bits that weren't clear to me, always a big help.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129829867266324872005-10-20T12:37:00.000-05:002005-10-20T12:37:00.000-05:00I know nothing about PPAD/TFNP, but am very intere...I know nothing about PPAD/TFNP, but am very interested in learning more. Do you know of a good overview reference, or at least one or two papers that cover the important aspects in some clarity?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129815092768661552005-10-20T08:31:00.000-05:002005-10-20T08:31:00.000-05:00Right, s has no predecessor but it must have a suc...Right, s has no predecessor but it must have a successor. I'll fix the post.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129781012336319312005-10-19T23:03:00.000-05:002005-10-19T23:03:00.000-05:00Thanks for that informative comment D. Sivakumar.I...Thanks for that informative comment D. Sivakumar.<BR/><BR/>I for one, had never heard of PPAD or TFNP but they sound quite natural.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129684980203508922005-10-18T20:23:00.000-05:002005-10-18T20:23:00.000-05:00Someone asked "How important a result is this?"Ver...Someone asked "How important a result is this?"<BR/><BR/>Very important. PPAD is a sub-class of TFNP, which consists of all "NP search problems" for which a solution is guaranteed to exist. An easy example is factoring an integer into its prime factors. Others include computing Nash equilibria, finding "Minkowski vectors" in lattices (vectors of length no more than a poly-time computable bound that were proved to exist by Minkowski), computing Brouwer fixed points, etc. There are also other cute problems like the one Lance mentioned, and also things like: given a circuit that maps n bits into n bits, either find an input that maps to all-0's or find two inputs that map to the same thing.<BR/><BR/>How one establishes the membership of a problem in TFNP (that is, how one shows that every instance has a solution) decides which sub-class of TFNP it goes into. Two papers --- one by Megiddo and Papadimitriou and one by Papadimitriou, circa 1990 --- placed several problems into this class. The type of techniques used include the use of pigeon-hole principle (as in the lattices example and the circuit example above), the use of parity arguments (as in Sperner's Lemma, Brouwer fixed points and Nash), simple graph-theoretic principles (every directed acyclic graph has a sink), etc.<BR/><BR/>Besides being natural bridges to much of classical mathematics, problems in TFNP tend not to be NP complete (where's the decision here?!), are not often polynomial-time solvable, have formed the bases of public-key cryptosystems (factoring and lattices), admit worst-case/average-case equivalence, etc.<BR/><BR/>These are truly curious beasts. On a more speculative note, it is conceivable that we separate P and NP by showing that one of these problems cannot be solved in polynomial time.<BR/><BR/>What exactly does PPAD complete mean? That every problem whose "guarantee of solution" comes from a certain type of parity argument can be reduced to the computation of Nash equilibria on a game with 4+ players. No more, no less --- our understanding of these problems is even worse than our understanding of the "famous" NP-complete problems.<BR/><BR/>SivaD. Sivakumarhttps://www.blogger.com/profile/05750992965116762335noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129683477113654572005-10-18T19:57:00.000-05:002005-10-18T19:57:00.000-05:00It is essentially one of the strongest "hardness"...It is essentially one of the strongest "hardness" results that one could hope to prove for the problem. Most people believe that PPAD-complete problems do not have polynomial-time algorithms, I think.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129673719836449302005-10-18T17:15:00.000-05:002005-10-18T17:15:00.000-05:00How important a result is this?How important a result is this?Anonymousnoreply@blogger.com