Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Two Theorems this blog missed

Expand Messages
  • GASARCH
    I warned Lance to wait until early Jan to post 2009 Complexity Year in Review. It was my fear that by posting it on Dec 28, 2009 he may miss out if someone
    Message 1 of 1 , Jan 20, 2010
    • 0 Attachment
      I warned Lance to wait until early Jan to post 2009 Complexity Year in Review. It was my fear that by posting it on Dec 28, 2009 he may miss out if someone proves P &ne NP on Dec 29, 30, or 31st during 2009.

      That did not happen and the review was fine. However, we did miss out on two of the biggest math stories of 2009. Not because they happened on Dec 29,30, or 31, 2009. Not sure why we missed them. But here they are.
      1. The Fundamental Lemma was proven. I won't embarrass myself by even trying to blog on it, but will instead point to a blog that did report on it: here. I found out about it when I saw it listed in Time Magazine as one of the top science stories of the year. The results seems to be really important.
      2. The Fundamental Pizza was proven. This was proven in 2009 but seems to have gotten attention on some blogs recently. Unlike The Fundamental Lemma this one I can state. Can I prove it? I doubt it--- it was conjectured 40 years ago. The paper is here. Here is the result:

        A waiter picks a point on a pizza and makes N slices through that point. Each slice has the same angle. One player gets every other slice and the other gets the other every other slice. Will they each get the same amount? This problem has now been completely solved:
        1. If the point is in the center then yes.
        2. If any of the slices happens to go through the center then yes. (Henceforth assume that no slice goes through the center.)
        3. If N=1 or N=2 or N &equiv 3 mod 4 then the person who gets the slice that has the center gets more.
        4. If N &ge 5 and N &equiv 1 mod 4 then the person who gets the slice that has the center gets less.
      This result did not make Time magazines list of one of the top science stories of the year. It wasn't even reported on this blog which it should have been. However, I can state it and I suspect I can read the paper if I brush up on my High School Trig. Hence its one of my favorite theorems of the year.

      --
      Posted By GASARCH to Computational Complexity at 1/20/2010 09:58:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.