Wednesday, May 20, 2009

two very nifty complexity theorems

theorems #2 and #3 here

(also one theorem, #1, that I can't appreciate and can't follow the proof of; and two theorems, #4 and #5, where the definitions used are new to me and I'm having trouble seeing the significance)

Incidentally, I don't find them sidesplitting as Aaronson does. YMMV, but if I were looking for a word for what he seems to be trying to get at, I'd probably call them something like "twisty" or "subversive," not sidesplitting.


Post a Comment

<< Home