tag:blogger.com,1999:blog-3722233.post4633927890943367371..comments2019-10-14T12:11:35.608-04:00Comments on Computational Complexity: The Solution to the Mark-Betty GameLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-28492867101184044312010-08-09T16:04:22.933-04:002010-08-09T16:04:22.933-04:00Anon who wants a copy of my manuscript on the game...Anon who wants a copy of my manuscript on the game- email me your email address and<br />I'll email it to you (unless you already<br />have it).GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61890810075492046412010-08-09T07:51:25.147-04:002010-08-09T07:51:25.147-04:00bill + lance, can you make sure to have an updated...bill + lance, can you make sure to have an updated blog post at the end of the day (okok I aint pushy, maybe in a few days then) with something on that paper everyone is talking about. <br /><br />It has generated enough hype to warrant a post at the prestigious weblog.fortnow.com site.<br /><br />xxx<br /> xAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39455907075138229322010-08-08T21:52:05.646-04:002010-08-08T21:52:05.646-04:00Dick Lipton has now posted something on the proof:...Dick Lipton has now posted something on the proof:<br /><br />http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/DaveMBhttp://www.cs.umass.edu/~barringnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61150793122405866392010-08-08T20:31:06.925-04:002010-08-08T20:31:06.925-04:00Here is a 100-page writeup of the proof:
http://w...Here is a 100-page writeup of the proof:<br /><br />http://www.scribd.com/doc/35539144/pnp12pt<br /><br />It uses the FO(LFP) characterization of P and claims that any P algorithm must miss some fraction of some kind of SAT instances. The background sections on complexity are sensible. He's a mathematician with a respectable record but no published prior work in complexity. Which either means that he's made some naive mistake coming from the outside, or that his being outside our community gives him some special insight. Or both...<br /><br />I don't see any obvious reason this couldn't be right, though of course the way to bet is that it's wrong...DaveMBhttp://www.cs.umass.edu/~barringnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3522272536105765212010-08-08T19:24:28.460-04:002010-08-08T19:24:28.460-04:00http://www.hpl.hp.com/personal/Vinay_Deolalikar/ ....http://www.hpl.hp.com/personal/Vinay_Deolalikar/ .... did he really prove P != NP??Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1054118096669467972010-08-08T18:14:08.238-04:002010-08-08T18:14:08.238-04:00it seems the whole umd website is down for a while...it seems the whole umd website is down for a while, so i can't access the writeup. really like to take a look though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64248271904769220322010-08-08T16:17:17.152-04:002010-08-08T16:17:17.152-04:00Any news about this new claim of P!=NP?Any news about this new claim of P!=NP?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37522682989536881482010-08-05T18:14:07.203-04:002010-08-05T18:14:07.203-04:00OK, it looks like you can easily take any family o...OK, it looks like you can easily take any family of Betty-strategies successful against f(n) in the finite game, and combine them into one successful against O(f(n)) in the infinite game.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76561209582599567422010-08-04T17:50:39.307-04:002010-08-04T17:50:39.307-04:00Ooh, I have a question!
Let f(n) be some nondec...Ooh, I have a question! <br /><br />Let f(n) be some nondecreasing function again.<br />Suppose the players now alternate playing on an *infinite* board. Mark wins if at any point there is some row/column A, and some n, such that Mark's additive surplus <i>in the first</i> n <i>entries of</i> A exceeds f(n).<br />When does Mark win?<br /><br />Of course, Mark can pick any target n and borrow a strategy from the finite game; so he wins for some f(n) = Omega(sqrt(n)) by the known result.<br /><br />The question is whether Betty can win for some f(n) not too much larger than sqrt(n). It might be possible to adapt the known Betty-strategy to work for all n simultaneously; I just don't have time to study the question. (Nice posts by the way.)Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12755167788917319652010-08-04T12:30:13.829-04:002010-08-04T12:30:13.829-04:00It was Reinhard Selten who memorably remarked that...It was Reinhard Selten who memorably remarked that "Game theory is for proving theorems, not for playing games." <br /><br />Selten was articulating a Great Truth, in the sense that its converse is a Great Truth too. The point being, it is *not* necessary that everyone do mathematics with the same motives (whether pure or applied) ... such uniformity would not even be desirable. <br /><br />Similarly, von Neumann advocated a mixed strategy (1947): <i>"When (mathematical style) becomes baroque, then the danger signal is up ... the only remedy seems to me to be the rejuvinating return to the source: the reinjection of more or less directly empirical ideas. I am convinced that this is a necessary condition to preserve the freshness and vitality of the subject, and that this will remain equally true in the future.''</i>John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30061377723735986912010-08-04T09:57:11.735-04:002010-08-04T09:57:11.735-04:00Anon 2- Oh, good point, once row or col is filled...Anon 2- Oh, good point, once row or col is filled up and Ben has<br />the required surplus the game ends,<br />so it need NOT go n^2/2 turns.<br /><br />Thanks for the correction.<br /><br />Others- as for who cares about this game or closing the gap,<br />INSERT USUAL ARGUMENTS WHY IT IS GOOD TO STUDY QUESTIONS WITH NO<br />IMMEDIATE APPLICATION.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26826374819513615012010-08-04T09:00:41.500-04:002010-08-04T09:00:41.500-04:00Apparently, I didn't follow up with the furthe...Apparently, I didn't follow up with the further intuition that I had. I am surprised by the fact that Betty's position is asymptotically defensible at all. My sense was that at some [finite] board size, regardless of f(n), Betty's position would be become hopelessly indefensible.Davidnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31261987464923268672010-08-04T03:10:47.587-04:002010-08-04T03:10:47.587-04:00Ok, I am looking at Beck's work now, it seems ...Ok, I am looking at Beck's work now, it seems that these questions are "interesting for their own sake", going back to Erdos...<br /><br />But besides Jozef Beck himself, would anybody else care about closing the \sqrt(log n) gap?<br /><br />If there is an expert here, please let me know whether/why this is (not) interesting. Thanks!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-605498215142994612010-08-04T01:51:53.752-04:002010-08-04T01:51:53.752-04:00In the write-up I am confused on one point: Once ...In the write-up I am confused on one point: Once there is a good row or column you write that Mark always plays there but you also say that the game runs for n^2/2 rounds. Won't the row be filled up long before that?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34152456765684680282010-08-04T01:28:59.576-04:002010-08-04T01:28:59.576-04:00Would it have any interesting consequences to clos...Would it have any interesting consequences to close the gap?Anonymousnoreply@blogger.com