平均時・最悪時の話

djbがなんか言ってるのでメモ。

格子の例は強い意味での平均時/最悪時帰着になっているので、広く宣伝されているわけですが、よく「強い意味で」というところが省略されているので、誤解を招いているようです。
djbが指摘しているように離散対数系のランダム自己帰着性は古くから知られている話なので、誤解を招く表現は確かによくないですね。はい。