This work is licensed under a
Creative Commons License.
|
Friday, April 01, 2005
Another Breakthrough!
Posted by Lance
Speaking of space complexity, Adam Kalai, Adam Klivans and Rocco Servedio have extended Reingold's result to show that every language in randomized logarithmic space has a deterministic log-space simulation, i.e., RL = L. Cool.You can find a copy of their paper here.
5:44 AM
# 5 comments
-
Should there be a qualifier here that it's April 1st?
-
I've shown that every problem in EXPSPACE can be solved by spitting on the sidewalk and analyzing the bubbles in the resultant globule.
-
What happend ? NP=P is not good enough for being a prank anymore ?
-
The link doesn't work!
-
nice one!!!
Links to this post:
Weblog Home
Archives
