Monday, October 12, 2009

The Molly Solution

This week Bill and I are both at the Dagstuhl Workshop on Algebraic Methods in Computation Complexity. I'll try to cover some of the talks and discussions on the blog and on Twitter.

Called home last night and had the following conversation with my 11-year old daughter.

Molly: I was thinking about this P/NP problem. What do P and N stand for?

Lance: You probably won't understand but P stands for "Polynomial-Time" and N stands for "Nondeterministic"

Molly: Well, if P and N were random variables then P=NP if N equals one.

An old joke, but my daughter had figured it out all on her own. So I answered her with the only response I could give.

Lance: Or if P equals zero.


  1. This joke gets VERY old quickly.
    I suppose you can forgive an 11 year old for using it though...

  2. that is so funny...

  3. a new paper appeared at arxiv saying that solves P vs NP. I'm not sure how serious this one is.

  4. I'm not sure how serious this one is.

    Well, one big clue is that the paper claims that SAT might be in P without leading to P=NP. The explanation of why the proof doesn't naturalize is a nice touch.

  5. Its sad how one works on easier and easier problems as one gets older