しました
http://d.hatena.ne.jp/ita/20080312/p1
でも間違えてるかも。チェックのためこれ読んでるけど
http://www.scottaaronson.com/writings/limitsqc-draft.pdf
激しく面白い。英語がわりと読めて計算というものに興味があるなら、今から７日以内に読まないと死にます。
タイムマシンを作るとNP完全問題を多項式時間で解けるからタイムマシンは不可能、とかいう面白い議論を展開してます。そうかイーガンのオラクルに出てきた議論はそのへんが絡んでるのか。
あとは普通の計算機にNP完全問題を計算させて自分は光速に近い宇宙船で旅をしてきて帰ってくれば「自分の時間では」多項式時間で計算が終わってる、とか。なるほど人類全員がコールドスリープすれば計算機能力はものすごいことになるな。
