tag:blogger.com,1999:blog-8666091.post4429288752881571999..comments2022-01-21T17:46:48.037+01:00Comments on The Reference Frame: Comparing the depth of the millennium problemsLuboš Motlhttp://www.blogger.com/profile/17487263983247488359noreply@blogger.comBlogger50125tag:blogger.com,1999:blog-8666091.post-3682393173687583042013-05-08T20:42:12.541+02:002013-05-08T20:42:12.541+02:00Your argument applies to both checkers and chess b...Your argument applies to both checkers and chess but there is an additional factor in chess, initiative, which is more important, and so the true reason chess is a draw is different ("margin of draw" because advantages may not be large enough to checkmate).Joe Shipmannoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-42540079679759417792013-05-08T19:28:10.936+02:002013-05-08T19:28:10.936+02:00For Banach Spaces examples are already known of bo...For Banach Spaces examples are already known of bounded operators with no invariant subspace. For Hilbert space the answer is unknown (for finite or uncountable dimension there is always a nontrivial invariant subspace so one can restrict attention to L2 (or l2)).Joe Shipmannoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-71441370077088501112013-05-08T17:10:54.693+02:002013-05-08T17:10:54.693+02:00Hi again, Eugene. Possibly Lubos will consider th...Hi again, Eugene. Possibly Lubos will consider these posts off topic, but I don't think so. They are deep questions that relate quite directly to the millenium problems P=NP? and the Riemann Hypothesis.<br /><br />And I wouldn't be so quick to judge yourself non-expert -- you quite accurately nailed the significance of backward calculation. It's not that "a plan" by either competitor is meaningful -- it's that the two-player macro plan is indifferent to winners and losers; the continuous function bounded by the start and the end of the game theoretically has a critically singular point independent of where the game begins or ends. As you and Lubos have pointed out, for many midgame or endgame problems one can identify a set of perfect information that predicts the conditional outcome. What is more useful for us to know (mathematically), is a way to generalize the problem without boundary conditions, avoiding all that "messy stochastic" stuff that Lubos spoke of. Easier siad than done, of course.<br /><br />Ten years ago I wrote a paper, "P = NP if time is probabilistic," that never got any traction. I went on and developed some of the ideas for a paper presented at necsi ICCS 2006, and forgot about it -- the main theme is the search for an n-dimensional equilbrium function that would obviate boundary conditions. It's retrievable online at fqxi.org/data/forum-attachments/P__NP.pdf if you or anyone else is interested.<br /><br />I decided to mention the paper here because it broadly attacks what we've been discussing, in terms of a love that Lubos and I both share for Analysis, i.e., the mathematics of continuous functions -- which is exactly what the "backward calculation" to which you refer, requires -- i.e., reversibility. The summary contains commentary on string theory as a self-organized phenomenon, and the Riemann hypothesis as an equilibrium function on the complex sphere.<br />All best,<br />TomT H Raynoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-65160168658506521922013-05-08T06:13:04.017+02:002013-05-08T06:13:04.017+02:00Dear Joe, right.
Didn't you mean Banach spa...Dear Joe, right. <br /><br /><br />Didn't you mean Banach space instead of the Hilbert space? "Banach" is what would make it a topic close to what my uncle has studied for decades. "Hilbert" makes it sound more physics-y but it's probably a wrong description of the problem.<br /><br /><br />I am not familiar with the problem and it's sort of hard to imagine that there is any unsolved problem of this Ansatz among the operators that are non-pathological from a physics viewpoint. It sounds too straightforward...Luboš Motlhttp://motls.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-8666091.post-76046311705014972802013-05-08T06:09:46.664+02:002013-05-08T06:09:46.664+02:00Thanks for your comments. I don't believe that...Thanks for your comments. I don't believe that my argument why it should be a draw applies more to checkers than chess.<br /><br /><br />Checkers is much closer to "drawing matches" because the length of the moves isn't as variable as it is for chess, so the precise frequency in timing may be more important. It's still a draw, you said.<br /><br /><br />It's also much harder to go through chess configurations because the pieces are inequivalent to each other so the number of configurations is about 16! * 16! times greater, if I exaggerate a bit.Luboš Motlhttp://motls.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-8666091.post-19842499240632629212013-05-08T04:06:19.812+02:002013-05-08T04:06:19.812+02:00Good review, my contribution to the RH problem lon...Good review, my contribution to the RH problem long ago http://thespectrumofriemannium.wordpress.com/2012/11/07/log050-why-riemannium/ CheersΘ³Σx² - ∂³Σx² - ΘΣhttp://twitter.com/riemanniumnoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-62600792392743189082013-05-08T01:32:55.210+02:002013-05-08T01:32:55.210+02:00I agree with you that the Riemann Hypothesis is pr...I agree with you that the Riemann Hypothesis is probably the deepest, and I also agree that even if P=NP that might not be of practical importance. However, it might also be of tremendous practical importance, which you shouldn't rule out. As you point out, Aaronson's opinion that factoring is an easy probem but 3SAT is a hard problem (I mean "easy" and "hard" in the sense of being able to answer small instances of the problems with high confidence by applying physics as well as math) is faith-based, while others have faith that quantum computers can't be built and factoring is hard, and still others might have faith that an effective way to calculate matrix permanents might be found (I am rooting for Leslie Valiant to adapt Scott's Boson Sampling work to accomplish this ;) ).<br /><br />My favorite problem that failed to make the "Millennium" list is the Invariant Subspace Problem--does every bounded linear operator on Hilbert space have a nontrivial invariant subspace? I think physicists' intuition might help here as much as it might help for the Riemann Hypothesis. Have you thought about this problem?Joe Shipmannoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-24772175415005595892013-05-08T00:59:24.990+02:002013-05-08T00:59:24.990+02:00Lubos,
First of all, you should note that Checker...Lubos,<br /><br />First of all, you should note that Checkers has been solved and shown to be a draw, using cleverly organized brute force.<br /><br />Probably 95% of chess grandmasters believe that with optimal play chess is a draw, but not for the reason you say. Your "babbling" actually gets at the intuitive reason that checkers is a draw, because the symmetry between White and Black is more important than the fact that Black moves first, since in checkers having an extra move doesn't help much.<br /><br />However, in chess, having an extra move is very important (this is also true in Go). Players will frequently sacrifice a pawn to obtain "the intiative" even when no other positional advantage is involved. There is a strong consensus that having White in chess is a significant advantage. The reason chess is thought by most grandmasters to be a draw is that the advantage is not quite large enough. There is a "margin of draw" which, as has become gradually clearer over the last 50 to 100 years, is larger than the amount of White's initial advantage. In very rough terms, white starts with an advantage worth a little less than half a pawn, but an advantage of a full pawn is just barely enough to win (typically, high-level games in which one player has an extra pawn but the other player has any nontrivial compensating positional advantage turn out upon deep analysis to be drawn with correct play).<br /><br />For the game of Go, there is no margin of draw because the winner is determined by a point count at the end. The amount of advantage the first player (Black, in Go) has is a matter of debate, and the handicap given to White in tournaments to make the game even has risen slightly in recent decades but no one thinks it should be less than 4 points or more than 8 points.Joe Shipmannoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-83769053263263323002013-05-07T22:38:21.019+02:002013-05-07T22:38:21.019+02:00OK Lubos, I'll bite. Of the things I listed, ...OK Lubos, I'll bite. Of the things I listed, <i>exactly</i> which ones are "uninteresting engineering technicalities"? Can you even explain any one of them in enough detail to justify that opinion?Scott Aaronsonnoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-34869500015127023092013-05-07T19:53:09.493+02:002013-05-07T19:53:09.493+02:00Thank you, Lubos. I'm really enjoying this ex...Thank you, Lubos. I'm really enjoying this exchange. I think I may have responded to the points of your post in one to Eugene above.<br /><br />My conjectures stem mostly from Leslie Lamport's research into Buridan's Principle, which I find generalizes; i.e., using the arithmetic theorem that a point can simultaneously approach any other set of points -- provided that it is far enough away -- implies a singularity in every measurement function from an initial condition, involving a continuous range of variables.<br />TomT H Raynoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-64029179931030430342013-05-07T19:26:26.410+02:002013-05-07T19:26:26.410+02:00Hi, Eugene. I'm no expert on computer chess, ...Hi, Eugene. I'm no expert on computer chess, either. I don't have a handy reference (though that sounds like a research project I should undertake) -- yet I would be very surprised to find that an analysis of machine moves, even to the examination of source code, didn't contain information that could not be unencrypted by a competitor. <br /><br />Suppose otherwise -- that two programmers agreed in advance to share their strategies, and let the machines decide the moves, each of them armed with the others' strategy. The machines themselves would have the means to encrypt information in the course of the game, or it would be as pointless as a game of tic-tac-toe (naughts and crosses to the Brits). In other words, even human players who are good at the game and have memorized much literature and many games, are broadly aware of the others' best strategies. It's no competitive advantage at the master level.<br /><br />I am looking at the problem in terms of information. Just as G. Hardy said, "Chess problems are the hymn tunes of mathematics" -- what we get from a set of positions has nothing to do with the game itself; it has to do with a single "song" in the "hymnal." More than that, the initial song determines the order in which at least two other songs are to be sung, so we are getting what comes to resemble a random walk in the problem space. Because the total information is finite, albeit very large, it can be modeled as a random walk around an equilibrium point -- (which is a common model in economics theories today, taken from John Nash's discovery of the Nash equilibrium). <br /><br />There's a point here somewhere. :-) Ah, right -- it's that the players make choices of where the equilibria will fall. For the entire game, this will collapse to one point; if one knew before the game began, where that point is to exist, he could force all the moves, and make the winning choice of moves.<br />TomT H Raynoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-11421772095113655072013-05-07T19:10:38.791+02:002013-05-07T19:10:38.791+02:00Today has been sort of a simultaneous exhibition c...Today has been sort of a simultaneous exhibition chess match for you, right? Fielding questions from beginners to experts, duking it out with international heavyweights, writing lengthy technical yet accessible articles, and I see you've also been active on physics SE today, plus pursuing whatever fiendish plans you hatched to snag a Millennium Prize... I guess you're not happy unless your multitasking cerebrum is in absolute, terminal overload. <br /><br />If you were a chess world champion I would not peg you as Bobby Fischer (evil!) nor as Kasparov (relied too often on intimidation and sheer force of personality) but Kramnik. Here he is <a href="http://www.kramnik.com/eng/interviews/getinterview.aspx?id=61" rel="nofollow">talking about Vasily Smyslov</a>, but it is obvious he is also talking about himself:<br /><br />- How would you describe the seventh World Champion, Vasily Smyslov? <br /><br />- How can I express it in the right way? ... <br />He is truth in chess! Smyslov plays correctly, truthfully and has a natural style. By the way, why do you think he lacks that aura of mystique like Tal or Capablanca? Because Smyslov is not an actor in chess, his play is neither artistic nor fascinating. <br />But I am fond of his style. I would recommend a study of Smyslov's games to children who want to know how to play chess because he plays the game how it should be played: his style is the closest to some sort of 'virtual truth' in chess. He always tried to make the strongest move in each position. He has surpassed many other of the World Champions in the number of strongest moves made. As a professional, this skill impresses me. I know that spectators are more interested in flaws ... <br />ups and downs. But from the professional standpoint, Smyslov has been underestimated.Eugene Snoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-88413646869068114802013-05-07T17:58:23.837+02:002013-05-07T17:58:23.837+02:00Interesting, Tom. I think that everyone expects ch...Interesting, Tom. I think that everyone expects chess to be a draw for the same reason. There are many endings and the ending configuration is so far from the initial one and is connected by so many possible games in between that it can't possibly have a clear "greater proximity" to the white player or the black player. It's pretty much symmetric so given the diversity of possible reactions, almost every advantage of the white player may be transformed into an advantage of the black player, too. The draw is the only answer that sort of respects the symmetry of the stochastic messy games in between.<br /><br /><br />This babbling of mine is very far from a formal proof that chess is a draw. ;-) But more generally, games with many moves where a single move often has the same effect as several moves are likely to be draws if a draw is possible at all.<br /><br /><br />Your problem space vs time comments are interesting, too.Luboš Motlhttp://motls.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-8666091.post-42873480683718379682013-05-07T17:56:31.177+02:002013-05-07T17:56:31.177+02:00First, I join the congratulations on your MIT appo...First, I join the congratulations on your MIT appointment. I have been reading your book and the exchanges on this blog, etc. Don't think it fair to say LM not willing to learn these things ... think that first we have to define "these things" more rigorously. "Deeper, Interesting, more fundamental" seem to be vague and ill-defined because what "... things that emerged, more-or-less inevitably, from efforts to understand ..." are ub fact more or less fundamental depending on the definition of fundamental. Because I am not qualified to assert the superiority of either of your views of fundamental, I instead offer that a Justice once said he could not define smut but knew it when he saw it. I agree with LM in great part but hope this dialogue does continue because I am learning much from both of you.Robert Rehbocknoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-84921616275058368782013-05-07T17:55:59.313+02:002013-05-07T17:55:59.313+02:00Dear Tom, I am not an expert on computer chess by ...Dear Tom, I am not an expert on computer chess by any stretch of the imagination. However: as far as I know the only times when an outcome is guaranteed to be a draw are the positions encoded in endgame tablebases. At present, all possible positions with any six pieces still on the board are known and the outcomes -- win, lose or draw -- with best play on both sides are also known. Every node in every branch of the tree is known, so if two chess programs reach such a position their operators will quickly agree to a draw.<br /><br /><br />What you write about strategy-concealing randomizing subroutines comes as complete news to me. Perhaps you are right, if so I would appreciate a reference. In general, the programs do not "think" about strategy, and especially I don't think that they try to get inside their opponent's silicon brain and guess what plans it might be pursuing. It would be futile because the programs are not "making plans", at least not in the sense that we humans think of the term. <br /><br /><br />It is perhaps interesting that the best chess players are not chess programs but man-machine teams, with the humans calling the shots on each move after looking at the program's output. A comforting thought when one is worried about being supplanted by computers...Eugene Snoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-73195876757183490222013-05-07T17:52:37.341+02:002013-05-07T17:52:37.341+02:00Right, T H Ray. A surprising twist turning a weakn...Right, T H Ray. A surprising twist turning a weakness into a special advantage is rare but this sometimes gives new geniuses their flavor. They think different. In some cases, it's due to good luck, in others, it's due to their seeing a bit further than others.<br /><br /><br />If computers remain weak in some situations, I am afraid that it's because the programs don't have the sufficient empathy to expect imperfect decisions of the foe. "He will buy this trick of mine" is something that a human player may often do but a computer player may avoid such things because it may incorrectly assume that the human opponent is sort of more perfect and mechanical than it is.<br /><br />Otherwise I can't believe that there is any reason why computers shouldn't beat any human player today.Luboš Motlhttp://motls.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-8666091.post-26440774530480484782013-05-07T17:46:46.529+02:002013-05-07T17:46:46.529+02:00I see my dyslexia has gotten me in trouble again. ...I see my dyslexia has gotten me in trouble again. I was thinking black to respond (hence the reference to king side). It wasn't, however, my main point.T H Raynoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-22525965598557052252013-05-07T17:36:22.809+02:002013-05-07T17:36:22.809+02:00This is a very mixed baggage of results - most of ...This is a very mixed baggage of results - most of them are uninteresting engineering technicalities - but what's more important is that they're not results of one particular compact theory or structure. They're results in a vaguely defined discipline of mathematics. <br /><br /><br />But if you cherry-pick some nice results over here, it's still sensible to consider them isolated interesting results at various points of mathematics - results that tend to be studied by similar people, largely for sociological reasons. The same can't be said about the results in string theory that are really inseparable from each other.Luboš Motlhttp://motls.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-8666091.post-73053637005329534702013-05-07T17:33:15.097+02:002013-05-07T17:33:15.097+02:00It's not a surprise for me at all. I have know...It's not a surprise for me at all. I have known for years that the Internet is overfilled with trolls and imbeciles.Luboš Motlhttp://motls.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-8666091.post-6698628427683875012013-05-07T16:09:35.521+02:002013-05-07T16:09:35.521+02:00Ah, thanks, Lubos. I've learned something new....Ah, thanks, Lubos. I've learned something new. I thought it was a settled matter that a perfect chess match has to end in a draw, though I hadn't given any<br />thought to a formalized proof. On the other hand, I conjecture that if such a proof can be written, It will surely be an existence proof.<br /><br />An existence proof for P = NP? would not suffice, regardless of whether the<br />answer is positive or negative. The main reason that the problem is so easy to understand in the first place, is that it begins with a construction (an assembled jigsaw puzzle, say) and asks if there is a way to assemble the pieces in at least as short a time as it took to make the cuts (assume that these are created by hand rather than pressed all at once onto the board).<br /><br />If there is a way to do that in one case, the same general algorithm can be applied to<br />all cases in that class. For instance, take the traveling salesman problem with only a few nodes where the optimum time is known -- increase the complexity by<br />n nodes and call it the problem space. It's obvious that the construction one used to solve the easy problem does not satisfy the problem space of the hard one. Just as one might write a program to optimize assembly time for a 10-piece puzzle, which doesn't satisfy the requirement for optimizing assembly time for a 1000 piece puzzle -- just increasing processor speed, in fact, might even<br />allow a brute force program to assemble the 10 piece puzzle even faster than it was created.<br /><br />One obvious interest in P = NP? to the CS community, then, is to try and overcome the physical limitations of brute force computation by replacing it with an algorithm that transcends the problem space. <br /><br />TomT H Raynoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-80343786482027788812013-05-07T15:31:32.890+02:002013-05-07T15:31:32.890+02:00Scott having followed the argument I think I have ...Scott having followed the argument I think I have to side with LM because if you look at Grigori Perelman's proof for example it solves the problem but in it's proof it gives you no more idea of why it is so or natural as LM has sort of been expressing it.<br /><br />So the Poincaré Conjecture proof as good as it is has no natural extension at least at this stage that we can see. <br /><br />Solving the N vs NP problem may turn out to be just the same a solution with no use beyond that and I believe that is what LM is saying.<br /><br />I guess the question I would ask Scott is what makes you think that a proof of NP v P would lead to anything beyond a mechanical proof like Grigori Perelman's.LdBnoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-10275190706298124692013-05-07T15:22:12.933+02:002013-05-07T15:22:12.933+02:00LOL! Somehow the fact that I enter "enemy te...LOL! Somehow the fact that I enter "enemy territory," and wind up with way more upvotes than my bellicose host on his own turf (a surprise to me as well), gets twisted into yet another count against me... :-)Scott Aaronsonnoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-29113555834815109852013-05-07T15:18:15.690+02:002013-05-07T15:18:15.690+02:00Yes, Miles played 1. ..a6, for which Karpov had no...Yes, Miles played 1. ..a6, for which Karpov had not prepared. It's still vastly different from 1. h4. It's difficult to explain if you aren't a chessplayer and if you are, then I wouldn't need to explain, but in a nutshell, 1. ...a6, while passive, preserves many options and can transpose into many well-known openings. In fact, this move is routinely played very early in, e.g., the Najdorf Sicilian and the Ruy Lopez. It could also transpose to some kind of hedgehog formation etc. Whereas 1. h4 is over-committal, does not transpose easily into known openings, weakens the kingside, and is just plain ugly :)Eugene Snoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-37282547091216018422013-05-07T15:16:51.725+02:002013-05-07T15:16:51.725+02:00Annnnd ... I think I've located the problem, r...Annnnd ... I think I've located the problem, right here! You explain correctly that the interest of string theory doesn't come from its starting assumptions, but rather from how much comes out of those assumptions that wasn't explicitly put in. Then you assert it as obvious that the same can't possibly be true of complexity theory. To me --- i.e., to someone who's studied the subject much more than you have --- it's obvious that the exact opposite is the case. The PCP Theorem, the role of finite fields in escaping the relativization barrier, GMW and other amazing cryptographic protocols (like Gentry's homomorphic encryption scheme), the Unique Games Conjecture and its connections to geometry, SDP relaxation, the "dualities" between upper bounds for one problem and lower bounds for another problem ... none of these are things anyone was thinking about when they formulated the P vs. NP problem back in the 70s. Yet they're all things that emerged, more-or-less inevitably, from efforts to understand P vs. NP and related problems. If you can't be bothered to learn about these things, but want to persist in attacking complexity theory anyway for having "no surprises" (!!!), then I don't see any point in continuing this discussion.Scott Aaronsonnoreply@blogger.comtag:blogger.com,1999:blog-8666091.post-74379281955358430152013-05-07T15:07:00.443+02:002013-05-07T15:07:00.443+02:00UK Grandmaster Tony Miles once beat Karpov with a ...UK Grandmaster Tony Miles once beat Karpov with a rook pawn opening (as Black). The match was due to be televised as part of a weekly BBC chess tournament,but there was a strike by BBC workers on that day so no video footage of the game exists (shame) http://www.chessgames.com/perl/chessgame?gid=1068157&kpage=5James Gallagherhttp://jbg.f2s.com/quantum2.txtnoreply@blogger.com