tag:blogger.com,1999:blog-3722233.post115814396510299466..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: Putting the Pieces TogetherLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-1158338261708963722006-09-15T11:37:00.000-05:002006-09-15T11:37:00.000-05:00I agree--I'm a first year grad student and this po...I agree--I'm a first year grad student and this post and your last complexitycast were both really great.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158288281720601232006-09-14T21:44:00.000-05:002006-09-14T21:44:00.000-05:00ah yes, procrastination born of insecurity... n...ah yes, procrastination born of insecurity... <BR/><BR/>no wonder Groucho Marx never amounted to much as a complexity theorist "I would never publish any result so trivial that I could prove it"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158215714100146362006-09-14T01:35:00.000-05:002006-09-14T01:35:00.000-05:00That was a really inspiring blog...Thanks Lance.That was a really inspiring blog...Thanks Lance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158213981012693822006-09-14T01:06:00.000-05:002006-09-14T01:06:00.000-05:00After ages, have I liked something greatly by Lanc...After ages, have I liked something greatly by Lance! And I completely agree with the last anonymous; It indeed motivates me to do research.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158182287432796292006-09-13T16:18:00.000-05:002006-09-13T16:18:00.000-05:00I liked the blog. It gave me some confidence again...I liked the blog. It gave me some confidence again to pursue putting bits and pieces from here and there.<BR/><BR/>Thanks,<BR/>SKUAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158174689771046872006-09-13T14:11:00.000-05:002006-09-13T14:11:00.000-05:00The highlighting is kind of coolThe highlighting is kind of coolTeutschhttps://www.blogger.com/profile/07089392105100217471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158173270749571012006-09-13T13:47:00.000-05:002006-09-13T13:47:00.000-05:00Great quote from T. Tao.Thanks.Great quote from T. Tao.<BR/><BR/>Thanks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158159500233258392006-09-13T09:58:00.000-05:002006-09-13T09:58:00.000-05:00The following excerpt from a UCLA column on Fields...The following excerpt from a <A HREF="http://www.college.ucla.edu/news/05/terencetaomath.html" REL="nofollow">UCLA column on Fields medalist Terence Tao</A> is quite inspiring:<BR/><BR/>How does Tao describe his success? <BR/><BR/>"I don't have any magical ability," he said. "I look at a problem, and it looks something like one I've already done; I think maybe the idea that worked before will work here. When nothing's working out; then I think of a small trick that makes it a little better, but still is not quite right. I play with the problem, and after a while, I figure out what's going on. <BR/><BR/>"Most mathematicians faced with a problem, will try to solve the problem directly. Even if they get it, they might not understand exactly what they did. Before I work out any details, I work on the strategy. Once I have a strategy, a very complicated problem can split up into a lot of mini-problems. I've never really been satisfied with just solving the problem; I want to see what happens if I make some changes. <BR/><BR/>"If I experiment enough, I get a deeper understanding," said Tao, whose work is supported by the David and Lucille Packard Foundation. "After a while, when something similar comes along, I get an idea of what works and what doesn't work. <BR/><BR/>"It's not about being smart or even fast," Tao added. "It's like climbing a cliff; if you're very strong and quick and have a lot of rope, it helps, but you need to devise a good route to get up there. Doing calculations quickly and knowing a lot of facts are like a rock climber with strength, quickness and good tools; you still need a plan – that's the hard part – and you have to see the bigger picture." <BR/><BR/>His views about mathematics have changed over the years. <BR/><BR/>"When I was a kid, I had a romanticized notion of mathematics -- that hard problems were solved in Eureka moments of inspiration," he said. "With me, it's always, ‘let's try this that gets me part of the way. Or, that doesn't work, so now let's try this. Oh, there's a little shortcut here.' <BR/><BR/>"You work on it long enough and you happen to make progress towards a hard problem by a back door at some point. At the end, it's usually, 'oh, I've solved the problem.'" <BR/><BR/>Tao concentrates on one math problem at a time, but keeps a couple of dozen others in the back of his mind, "hoping one day I'll figure out a way to solve them. If there's a problem that looks like I should be able to solve it but I can't, that gnaws at me."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158159369856537962006-09-13T09:56:00.000-05:002006-09-13T09:56:00.000-05:00I agree with previous poster. We have managed to a...I agree with previous poster. We have managed to automate chess, even though the best algorithms still run in exponential time. Many new lines and refutations are nowadays discovered by computers alone and/or in combination with a human.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158156297734544782006-09-13T09:04:00.000-05:002006-09-13T09:04:00.000-05:00People will regularly say that unless P=NP, we can...People will regularly say that unless P=NP, we can't automate the process of proving theorems. But thats not really true, is it? Anything that you do, including proving theorems, we can in principle automate. P and NP don't separate man and machine, since people can't efficiently solve NP complete problems either. In principle computers should be able to prove hard theorems just as efficiently as people, which is to say, inefficiently.Anonymousnoreply@blogger.com