tag:blogger.com,1999:blog-3722233.post8196532692182063373..comments2024-07-18T10:10:20.703-05:00Comments on Computational Complexity: Poset Games are PSPACE-completeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-46234704803219606222012-09-26T18:48:19.876-05:002012-09-26T18:48:19.876-05:00No, I don't think so. PSPACE (and most other c...No, I don't think so. PSPACE (and most other complexity classes) deal with languages, i.e., questions that have YES/NO answers. In the POSET game case, "Is there a strategy for player one to win?" There is no requirement for a machine that solves such a problem to actually produce the proof. So, if this is indeed the case, a machine can just report YES on all (relevant) inputs and thus solve he problem efficiently. Compare for instance with COMPOSITE and FACTORING. In COMPOSITE you ask if a number is composite, answerable in polynomial time, whereas actually producing the prime factors takes exponential time.Bengt J. Nilssonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88265911470788680342012-09-26T02:12:12.837-05:002012-09-26T02:12:12.837-05:00You did know well. I only read about it, no so exp...You did know well. I only read about it, no so experienced about.Anonymoushttps://www.blogger.com/profile/05340322713209271913noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1890325477046877032012-09-25T10:02:58.513-05:002012-09-25T10:02:58.513-05:00Is Chomp easy to solve in general? As far as I re...Is Chomp easy to solve in general? As far as I remember, it's known that the first player on a full-rectangular board has a winning strategy, but it is not at all constructive.Kylehttps://www.blogger.com/profile/02448231492905040705noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69161309671929473032012-09-20T18:45:02.287-05:002012-09-20T18:45:02.287-05:00But suppose the situation is that the first player...But suppose the situation is that the first player always wins for general POSET, yet it takes cost of PSPACE complete to find the winning strategy, the game is still PSPACE complete, or not?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42541800362844218302012-09-20T15:47:03.474-05:002012-09-20T15:47:03.474-05:00That still holds. Grier's result is about gen...That still holds. Grier's result is about general poset games. The Chomp family is an easy restriction of the general problem.Unknownhttps://www.blogger.com/profile/07167707679832856429noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44842532843280207452012-09-20T12:05:33.293-05:002012-09-20T12:05:33.293-05:00Hmm, I seem to remember that in Chomp[1] (a POSET ...Hmm, I seem to remember that in Chomp[1] (a POSET game) the first player always wins. Does this got disproven?<br /><br />[1]: http://en.wikipedia.org/wiki/ChompAnonymoushttps://www.blogger.com/profile/05340322713209271913noreply@blogger.com