再まとめ

第二日

機械の万能性と限界• 機械は有限の文字列（算譜）で記述できる• 入力された算譜を実行する計算ができる（EVAL は認識可能）• しかし EVAL は判定可能ではない（対角線論法）• 様々な言語の判定不能性が帰着により示される

第三日
時間と空間の制限

13

計算量の考え方（原則） 1950～70年代• チューリング機械での計算にかかる時間（遷移の回数）や空間（訪れる欄の数）を考える

As soon as an Analytic Engine exists, it will necessarily guide thefuture course of the science. Whenever any result is sought by its
aid, the question will arise—By what course of calculation canthese results be arrived at by the machine in the shortest time?
— Charles Babbage (1864)

結手問をな科解果順が得ろ学析にであようの機辿計るう。発関り算 とこ展は着す すのを、くれそる機方実かばれと械向現で最はきをづす
あも、重用けれる短い要いるば。時かとても必
間なな結のずでるる果とや•――

解析機関（Analytic Engine）「解析機関」『ウィキペディア日本語版』https://ja.wikipedia.org/w/index.php?title=%E8%A7%A3%E6%9E%90%E6%A9%9F%E9%96%A2&oldid=82653674）

13•

現実にかかる時間や空間をよく表している

それが入力の⾧さに応じてどう変るか函数として表す「⾧さ 𝑛 の入力なら必ず時間（や空間）が 𝑇 𝑛 以内で済む」
ような函数 𝑇 が計算量の尺度その函数の増大の速さに着目

特に 𝑛 の多項式以内か否かが重要113213定義
機械 𝑀 が多項式時間であるとは 或る多項式 𝑝 が存在し任意の⾧さ 𝑛 の任意の入力に対する 𝑀 の計算が時間 𝑝 𝑛 以内に終る（遷移 𝑝 𝑛 回以下で停止する）ことをいう
言語 𝐴 を認識する多項式時間の機械 𝑀 が存在するとき𝐴 は多項式時間認識可能であるという𝑛 の多項式以内である例
𝑛𝑛 の多項式以内でない例
2𝑛 𝑛

例 第一日のこの機械は時間 𝑛 + 1 以内に停止するのでMOREA は多項式時間認識可能「認識可能」の定義では 𝑥 ∉ 𝐴 のときは停止しないことを許していた
それに合せて「多項式時間認識」の定義は ⾧さ 𝑛 の入力 𝑥 について• 𝑥 ∈ 𝐴 のとき 𝑀 は 𝑥 を時間 𝑝 𝑛 以内に受理する• 𝑥 ∉ 𝐴 のとき 𝑀 は 𝑥 を時間 𝑝 𝑛 以内に受理しないとすべきでは？
そう定義しても「多項式時間2認識可能」の意味は変りません

1.05𝑛 log 𝑛5𝑛 + 4𝑛定義
機械 𝑀 が多項式時間であるとは 或る多項式 𝑝 が存在し任意の⾧さ 𝑛 の任意の入力に対する 𝑀 の計算が時間 𝑝 𝑛 以内に終る（遷移 𝑝 𝑛 回以下で停止する）ことをいう
言語 𝐴 を認識する多項式時間の機械 𝑀 が存在するとき
𝐴 は多項式時間認識可能であるという受理せずに時間 𝑝 𝑛 が経過したら不受理と確定できるので

𝑛!

𝑛多項式時間では「認識可能」と「判定可能」の違いはない

3（多項式時間認識可能な言語は補集合も多項式時間認識可能）

チャーチとチューリングの定立（続）「現実的な手間で計算できる」

入力が大きくなると手間が大違い

多項式時間認識可能

10

30

50

100

1000

1万

100万

1億

𝑛

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

𝑛

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒

2分

𝑛

1秒以内

1秒以内

1秒以内

1秒以内

1秒

2分

12日

3百年

𝑛

1秒以内

1秒以内

1秒以内

1秒

17分

12日

3万年 3百億年21秒以内

18分

36年

4京年

1017分

3京年

𝑛!

3.6秒 800京年

入力⾧ 𝑛 =

テープの形や読取り部の動き方など

チューリング機械の定義の細部は計算法が多項式時間であるかないかに影響を与えない「O 𝑛 であるかないか」など細かい量にはそれなりに影響がある

計算手順が解り易いように説明する

時間＝「基本的な操作の回数」と大雑把に考えてよい• 四則演算やビットの操作など• 機械語での命令数

13なぜ多項式時間か否かが重要か（チューリング機械で）

今後は一々チューリング機械を考えず

3131秒に100万回の処理ができるとしたときにかかる時間

多項式時
間
指数時
間

実際には 多項式時間の中での速さの差（𝑛 と 𝑛 の違いなど）も勿論重要なのですがこの講義では「多項式時間であるかないか」というより大きな違いに着目します

413513

なぜ多項式時間か否かが重要か

定義
機械 𝑀 が多項式空間であるとは 或る多項式 𝑝 が存在し任意の⾧さ 𝑛 の任意の入力に対する 𝑀 の計算が空間 𝑝 𝑛 以内である（テープ上で初めの欄の左右 𝑝 𝑛 個の範囲に留まる）ことをいう
言語 𝐴 を認識する多項式空間の機械 𝑀 が存在するとき𝐴 は多項式空間認識可能であるという多項式 𝑞 が存在して指数個（以上）の組合せから何かを探す場面は多い（組合せ爆発）
問題
PRIME

与えられた正整数（十進法で 𝑛 桁）が素数か判定それ未満の数（10 個ほどある）で割り切れるか全部調べれば判る
それよりも劇的に速く

問題
HAMILTON

入力⾧ 𝑛 のとき 2定理
多項式時間認識可能 ⟹ 多項式空間認識可能 ⟹ 指数時間認識可能

𝑛 の多項式時間で判定する方法が存在［AKS04］①（全頂点を一度づつ通る辿り方）② 多項式空間機械 𝑀 に対して多項式 𝑞 が存在し⾧さ 𝑛 の入力に対する 𝑀 の状況としてあり得るものは 2個以内

頂点の並べ方（𝑛! 個ある）を全部調べれば判る
𝑛 の多項式時間で判定する方法があるかどうかは判らない（多分なさそう）［AKS05］ M. Agrawal, N. Kayal and N. Saxena. PRIMES is in P. Annals of Mathematics, 160: 781–793, 2004.

問題

入力 正の整数 𝑋（を十進表示したもの）

PRIME

答

問題

入力 グラフ 𝐺

HAMILTON

答②① 空間を 1 使う（新たな欄に移動する）にも時間 1 かかるので与えられたグラフがハミルトン閉路をもつか判定

6

時間以内受理するのであれば時間 ≤ 2で受理する

始受

状況間の遷移関係

13※ PRIME は本当は多項式時間認識可能であることが今では判っているが𝑋 は素数か問題

入力 正の整数 𝑋（を十進表示したもの）

PRIME

答

問題

入力 グラフ 𝐺

HAMILTON𝐺 にハミルトン閉路はあるか定理

答

713※ PRIME は本当は多項式時間認識可能であることが今では判っているが𝑋 は素数か𝐺 にハミルトン閉路はあるか定理

PRIME や HAMILTON は多項式空間認識可能
入力

48581583386419 ÷
𝑛桁2= 24290791693209 あまり 1

3= 16193861128806 あまり 1⋮6306457

48581583386418=

PRIME や HAMILTON は多項式空間認識可能

𝑛 桁の割り算ひとつひとつは容易（𝑛 の多項式時間）

7703467 あまり 0（前指同の数じ行的場をに所覚多にえく上ての書お手きく間
し必がて要かよはかいなる）いが入力

12

3

4

56

𝑛 頂点

辺がちゃんと繫がった経路になっているか確かめるのは容易
123456

ダメ（3と4の間や6と1の間が繫がっていないので）123465ダメ（3と4の間や4と6の間が繫がっていないので）123546⋮654321813

経路の候補 𝑛! 個（前指同の数
じ行的場をに所覚多にえく上ての書お手きく間し必がて要か
よはかいなる）いが813入力 書換え規則の集合 𝑅 と文字列 𝑤

問題
SR

答

𝑅 による書換えを次々と 𝑤 に施して ε にできるか

入力 書換え規則の集合 𝑅 と文字列 𝑤

問題

但し 𝑅 の各規則 𝑢 → 𝑣 において (𝑢 の⾧さ) ≥ (𝑣 の⾧さ)

SR

答

𝑅 による書換えを次々と 𝑤 に施して ε にできるか

困難
そう（一般的な入力）問題

但し 𝑅 の各規則 𝑢 → 𝑣 において (𝑢 の⾧さ) ≥ (𝑣 の⾧さ)

SR

答

𝑅 による書換えを次々と 𝑤 に施すと可能な書換え方は毎回一通りしかなく やがて ε に達する

入力 書換え規則の集合 𝑅 と文字列 𝑤

問題

但し 𝑅 の各規則 𝑢 → 𝑣 において (𝑢 の⾧さ) > (𝑣 の⾧さ)

SR

答

𝑅 による書換えを次々と 𝑤 に施すと可能な書換え方は毎回一通りしかなく やがて ε に達する

定理
SR は多項式空間認識可能

入力

問題
SR問

※ 𝛴 = a, b の場合を考える（他のときも同様）

問題
SR

容
易
そう（特殊な入力）

しかしbabaaabb𝑤⇒ εかSR を各規則が(旧⾧さ) ≥ (新⾧さ)の場合に制限したもの? （次頁）

を更に定理
SR は多項式空間認識可能

SR を更に各規則が(旧⾧さ) > (新⾧さ)の場合に制限したもの

定理
SR は多項式時間認識可能な場合に制限したもの問題
SR

9定理（昨日）SR は認識可能（だが判定可能でない）∗

問題 可能な書換え方が毎回一通り
SR

𝑅, 𝑤 但し各規則が(旧⾧さ) ≥ (新⾧さ)𝑤 ⇒∗ ε か定理
SR は多項式空間認識可能𝑤⇒ε かどうか𝑥⇒𝑦𝑥⇒

ε かどうか調べればよい

𝑦問題
SRbbabbabb

或る 𝑧 ∈ 𝛴が存在して 𝑥 ⇒𝑥 = 𝑦 または 𝑥 ⇒ 𝑦⋮bbabaabb

babbabbb
bbbababb𝑤⇒
aa ⋯ aa かつ
aa ⋯ aa ⇒ε か？

経路の候補一本を覚える空間もない𝑤⇒
ε (?)

ε か？

𝑤⇒
aa ⋯ ab かつ
aa ⋯ ab ⇒ε か？

⋮1013

問

13𝑅, 𝑤 但し各規則が(旧⾧さ) ≥ (新⾧さ)𝑤 ⇒∗ ε か≤ 2 個の場合分け（成立つものが一つでもあるか調べる）

それぞれ≤ 2 個の場合分け𝑧 かつ 𝑧 ⇒𝑦

⇒ ●● かつ●● ⇒ ▲▲ か？という意味

す到べ達て済覚のえ文
る字空列
間をはない入力

9

次の関係を再帰的に用いて調べればよい

単純に⾧さ ≤ 2 の経路すべてを調べることはできないbabababb

テ書ー換
プえ上をで実）際
行にっ順て次み（れ機ば械よのい13𝑤 から書換えにより生じ得る文字列も⾧さ < 𝑛 であり その個数は < 2
書換え 2 回以内で 𝑤 から ε が得られる

答

SR

入力の⾧さが 𝑛 である（𝑤 の⾧さ < 𝑛）ときしたがって 𝑤 ⇒𝑅, 𝑤

SR

入力 書換え規則の集合 𝑅 と文字列 𝑤

問題

入力⇒ ★★ かつ★★⇒ ▲▲ か？

⋮深さ 𝑛⋮⋮
今ココ1113

複雑さの階層 問題の難しさの分類
ABA

多項式時間認識可能でなく多項式空間認識可能である問題が存在するかは未解決

SR

正則SR

MOREA
PRIME

多項式時間認識可能
HAMILTON

SR

多項式空間認識可能まとめ

多項式空間認識可能でなく指数時間認識可能である問題が存在するかも未解決

第三日時間と空間の制限• 時間計算量は「入力⾧ 𝑛 のとき時間 𝑇 𝑛 以内で計算できる」という形で測る（空間計算量も同様）• 多項式時間 ≒ 現実的な手間での計算• それに比べて多項式空間はいかにも強すぎて非現実的っぽい（指数個の調べ尽しができる）• しかし「多項式時間認識可能≠多項式空間認識可能」は未証明（不可能性の証明は難しい）

但し 多項式時間認識可能でなく指数時間認識可能である問題が存在することは判っている（対角線論法の応用）

指数時間
認識可能

判定可能
（時間制限なし）

SREVAL

認識可能

1213

1313