計算複雑性理論
独学した内容をまとめたものであり、間違いを含む場合がある
非公開scrapboxから引っ張ってきたものなので一部リンクが壊れている
ノーテーション
必ずしも一般的なものではない
$ xの$ 2^*へのコード化を$ \llcorner x \lrcornerと表記する
$ xのコード化した際の配列の長さを$ \|x\|と表記する$ \| x \| := |\llcorner x \lrcorner |
（有限）集合$ Aの全ての元のエンコードした配列の長さが一定の時、それを$ \|A \|と表す
たいてい$ \|A\| = \log |A|である
$ 2, \mathbf{2} := \{0, 1\}
$ \mathbb{B}, \mathbf{2}^* := 2^{<\omega}
参考文献