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.
Should there be a qualifier here that it's April 1st?
ReplyDeleteI've shown that every problem in EXPSPACE can be solved by spitting on the sidewalk and analyzing the bubbles in the resultant globule.
ReplyDeleteWhat happend ? NP=P is not good enough for being a prank anymore ?
ReplyDeleteThe link doesn't work!
ReplyDeletenice one!!!
ReplyDelete