[Computational Complexity] Two Theorems this blog missed
- 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.
- 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.
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 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:
- If the point is in the center then yes.
- If any of the slices happens to go through the center then yes. (Henceforth assume that no slice goes through the center.)
- 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.
- If N &ge 5 and N &equiv 1 mod 4 then the person who gets the slice that has the center gets less.
Posted By GASARCH to Computational Complexity at 1/20/2010 09:58:00 AM