15/03/01 07:28:54.43 NplpTsbd.net
対角線論法２ P5「辞書式順序(lexicographic order)」の説明が良いね
URLﾘﾝｸ(www.ocw.titech.ac.jp)
東京工大 ホーム > 大学院情報理工学研究科 > 数理・計算科学専攻 > 計算量理論
計算量理論 Computational Complexity Theory （ 渡辺 治 ） 更新日：2013年7月5日
第. 5. 章|. 計算複雑さ解析法＃２ 対角線論法
[PDF]計算複雑さ解析法＃2 対角線論法 - TOKYO TECH OCW
www.ocw.titech.ac.jp/index.php?module=General...file...
時間では計算できないが，. O. ( l 5). 時間では計算で. きる問題を示す方法である．
こうした差を示すことで初めて計算量に本質的. な意味が与えられる．
差がなければ，. 計算量の大小を議論する意味がなくな. るからだ． これはまた，. 計算複雑さの理論の最も ...