【シプサ】7 時間の複雑さ (その2)

シプサは、ちょっと離れると再開する敷居が高い。されど、こつこつ。

• まず、前回最後のあたりがぐだぐだになったので、そのあたりから。
  
  
• 「定理7.8 t(n)をt(n)>=nであるような関数とする。このとき、すべてのt(n)時間複数テープTuring機械に対して、それと等価なO((t^2)(n))時間単一テープTuring機械が存在する。」
  
  
  
  • まず、この定理がいっていることの理解を深める。
    
  • t:n->R+な関数tについて、TIME(t(n))という言語の集合をつくれる。TIME(t(n))に含まれる言語は、O(t(n))時間Turing機械で判定されるものに限る。これが基本情報。
    
  • ということは、t(n)時間複数テープTuring機械が判定する言語は、TIME((t^2)(n))に属している言語である、という感じなんだな。
    
  • (t^2)(n)が何をあらわしているのかわからない。(t(n))(t(n))ということか? これは説明を読んで理解することにする。
    
    
  • さて、説明の理解。これは文章ではなくて、紙に絵を書いて理解をこころみる。
    
  • ... お絵描き中 ...
    
  • 雰囲気はわかった。。。(t^n)(n)は、(t(n))(t(n))のことのようだ。先へ進む。
    
  
  
  
• 「定理7.11 t(n)をt(n)>=nであるような関数とする。このとき、すべてのt(n)時間非決定性Turing機械に対して、それと等価な2^(O(t(n)))時間決定性単一テープTuring機械が存在する。」
  
  
  
  • うーん。これもなんとなく雰囲気をつかんだ。
    
  • 先々、必要になったときに、理解を深めることにする。(今は興味がわかない)
    
  
  
  
• ここから「7.2 クラスP」。
  
  
• そうか、決定性単一テープTuring機械で多項式時間判定できる言語のクラスがクラスPなんだ。
  
• そして、クラスPである、ということと、現実の電子計算機で計算を実行できるということは経験上等価であると。少くとも第一近似または突破口としてはよし。
  
• クラスPという概念は、「妥当な」計算モデルの変更によって影響を受けない。さらばTuring機械、ということか!?
  
• クラスPの概念を理解した。
  
  
• 気になるところを確認。
  
• 「与えられた数の素因数を求める一つの方法は、すてのの可能な序数を調べてみることである。この探索空間のサイズは指数的なので、」
  
  
  
  • 素因数って何だっけ?
    
  • 素因数：整数の因数である約数のうち、素数であるもの。
    
  • 因数って何だ?
    
  • 因数：一つの数や整式が、いくつかの数や整式の積の形で表されるときの、その個々の数や整式のこと。
    
  • 探索空間のサイズは?
    
    
    
    • 10進数で入力を表現する。
      
    • n=1;数=1 -> 1
      
    • n=2;数=10 -> 10
      
    • n=3;数=100 -> 100
      
    • n=4;数=1000 -> 1000
      
    • なるほど。入力のサイズnに対して調べるべき対象の数は、10^nになっている。
      
    
    
  
  
  
• 「項目1は、Pが数学的に頑強なクラスであることを示している」
  
  
  
  • 頑強(robust)というのは、前にでてきたような、どこだっけ。
    
  • 索引を調べるが、なかった。先へ進む。。。
    
  
  
  
• その計算が多項式時間でいけるかどうかを検討する際のポイント
  
  
  
  • 問題の符号化に関連すること(表現から内部表現の構成、他の表現も使うならばそれへの変換、またはこれらの逆変換など)が多項式時間でできるかどうか。
    
  • アルゴリズムのステージ数は多項式時間か。
    
  • アルゴリズムの各ステージの実行ステップは多項式時間か。
    
  
  
  
• 気になること。数字の一進表現は指数的だが、二進表現は多項式的?
  
  
  
  • まず、一進表現。
    
  • n=1;16進数=1 -> 1
    
  • n=2;16進数=10 -> 16個
    
  • n=3;16進数=100 -> 256個
    
  • まあ、これは指数的。
    
  • 次に二進表現。
    
  • n=1;16進数=1 -> 1個
    
  • n=2;16進数=10 -> 5個 (1 0000)
    
  • n=3;16進数=100 -> 9個 (1 0000 0000)
    
  • おお、n^2程度だ。
    
  
  
  
• う、これから、例としてグラフ理論が多くなるのか。。。
  
  
• 「定理7.14 PATH∈P」
  
  
  
  • 気になるところを調べる。
    
  • 全数探索は本当に指数的か?
    
  • グラフ Gの節点数をmとする。
    
  • sからtへの経路が存在するならば、それは各節点をたかだか1回しかとおらない。なぜなら、2回とおるということはループ構造があるということであり、ループしなきゃいいんだから。
    
  • するとG内に存在する経路とは高々m個の節点の列である。
    
  • ではこのような節点の列が何個あるかというと、始点をsとしたものは、(m-1) + (m-1)(m-2) + (m-1)(m-2)(m-3) + ... + (m-1)(m-2)...(2)(1)かな?
    
  • これが指数的か多項式的か?
    
  • わからない。。。
    
  • いかん、グラフ理論または離散数学の勉強をせねば。
    
  • とりあえず今は先に進む。
    
  
  
  
• 「定理7.15 RELPRIME∈P」
  
  
  
  • これはアルゴリズムとデータ構造のときに検討したので、まあわかる。
    
  
  
  
• 「定理7.16 すべての文脈自由言語はPの要素である」
  
  
  
  • これ、ぼやぼやしている、日を置いて再度考える。
    
  
  

またまた最後ぐだぐだになったが、とりあえずクラスPがおわった。
次回はクラスNP。