現代数学の系譜11 ガロア理論を読む12

220 ：１３２人目の素数さん：2015/03/01(日) 07:28:54.43 ID:NplpTsbd.net

対角線論法２　P5「辞書式順序(lexicographic order)」の説明が良いね
http://www.ocw.titech.ac.jp/index.php?module=General&action=T0300&JWC=20131226715015
東京工大 ホーム > 大学院情報理工学研究科 > 数理・計算科学専攻 > 計算量理論
計算量理論 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). 時間では計算で. きる問題を示す方法である．
こうした差を示すことで初めて計算量に本質的. な意味が与えられる．
差がなければ，. 計算量の大小を議論する意味がなくな. るからだ． これはまた，. 計算複雑さの理論の最も ...