Wednesday, September 13, 2006

Putting the Pieces Together

A student proves what I feel is quite a nice result but the student laments that the proof was easy, they had simply put together various tools from earlier papers. Guess what? That's called research. Every mathematical result is simply of combination of logical statements put together in the right way. But unless P=NP we cannot automate this process. Our job is to figure out how to combine results and techniques we already know to prove things we didn't know before.

Most proofs seem simple once we've proved them. With some notable exceptions, every proof has (at most) one new idea, the rest just connecting the dots through techniques we've seen before.

From the outside or from the eyes of a young graduate students, research seems like a magical process that mathematicians somehow pull proofs out of a hat. Successful theorists are not magicians, just people who have read and understood techniques from a variety of sources and find news ways to put those techniques together to solve the problem on hand.


  1. 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.

  2. 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.

  3. The following excerpt from a UCLA column on Fields medalist Terence Tao is quite inspiring:

    How does Tao describe his success?

    "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.

    "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.

    "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.

    "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."

    His views about mathematics have changed over the years.

    "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.'

    "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.'"

    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."

  4. Great quote from T. Tao.


  5. The highlighting is kind of cool

  6. I liked the blog. It gave me some confidence again to pursue putting bits and pieces from here and there.


  7. After ages, have I liked something greatly by Lance! And I completely agree with the last anonymous; It indeed motivates me to do research.

  8. That was a really inspiring blog...Thanks Lance.

  9. ah yes, procrastination born of insecurity...

    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"

  10. I agree--I'm a first year grad student and this post and your last complexitycast were both really great.