再第三日
時間と空間の制限

13

再まとめ

第二日

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

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）

113計算量の考え方（原則） 1950～70年代
1. チューリング機械での計算にかかる時間（遷移の回数）や空間（訪れる欄の数）を考える
現実にかかる時間や空間をよく表している

2. 入力の長さに応じてどう変るか函数として表す「長さ 𝑛 の入力なら必ず時間（や空間）が 𝑇 𝑛 以内で済む」と保証されるような函数 𝑇 が計算量の尺度

3. その函数の増大の速さに着目
特に 𝑛 の多項式以内か否かが重要

4. 計算量○○で解ける ＝ 計算量○○の算法が存在する「如何なる方法でも××できない」と示すのが究極の目標だがそれはしばしば難しい

213定義機械 𝑀 が多項式時間であるとは 或る多項式 𝑝 が存在し任意の長さ 𝑛 の任意の入力に対する 𝑀 の計算が時間 𝑝 𝑛 以内に終る（遷移 𝑝 𝑛 回以下で停止する）ことをいう
言語 𝐴 を認識する多項式時間の機械 𝑀 が存在するとき𝐴 は多項式時間認識可能であるという𝑛 の多項式以内である例
𝑛𝑛 𝑛𝑛2 log 𝑛5𝑛3 + 4𝑛𝑛 の多項式以内でない例
2𝑛22

例 第 1 日のこの機械は時間 𝑛 + 1 2 以内に停止するのでMOREA は多項式時間認識可能

𝑛1.05𝑛𝑛log 𝑛𝑛!

313定義機械 𝑀 が多項式時間であるとは 或る多項式 𝑝 が存在し任意の長さ 𝑛 の任意の入力に対する 𝑀 の計算が時間 𝑝 𝑛 以内に終る（遷移 𝑝 𝑛 回以下で停止する）ことをいう
言語 𝐴 を認識する多項式時間の機械 𝑀 が存在するとき𝐴 は多項式時間認識可能であるという「認識可能」の定義では 𝑥 ∉ 𝐴 のときは停止しないことを許していた
それに合せて「多項式時間認識」の定義は 長さ 𝑛 の入力 𝑥 について• 𝑥 ∈ 𝐴 のとき 𝑀 は 𝑥 を時間 𝑝 𝑛 以内に受理する• 𝑥 ∉ 𝐴 のとき 𝑀 は 𝑥 を時間 𝑝 𝑛 以内に受理しないとすべきでは？
そう定義しても「多項式時間認識可能」の意味は変りません
受理せずに時間 𝑝 𝑛 が経過したら不受理と確定できるので多項式時間では「認識可能」と「判定可能」の違いはない（多項式時間認識可能な言語は補集合も多項式時間認識可能）313

チャーチとチューリングの定立（続）「現実的な手間で計算できる」（チューリング機械で）多項式時間認識可能
テープの形や読取り部の動き方など

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

今後は一々チューリング機械を考えず計算手順が解り易いように説明する

時間＝「基本的な操作の回数」と大雑把に考えてよい• 四則演算やビットの操作など• 機械語での命令数413なぜ多項式時間か否かが重要か
入力が大きくなると手間が大違い
1030

50

100

1000

1万

100万

1億𝑛

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

𝑛

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒

2分

𝑛2

1秒以内

1秒以内

1秒以内

1秒以内

1秒

2分

12日

3百年

𝑛3

1秒以内

1秒以内

1秒以内

1秒

17分

12日

3万年 3百億年

2𝑛

1秒以内

18分

36年

4京年

10𝑛

17分

3京年

𝑛!

3.6秒 800京年

入力長 𝑛 =

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

多項式時
間
指数時
間

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

なぜ多項式時間か否かが重要か
指数個（以上）の組合せから何かを探す場面は多い（組合せ爆発）
問題
PRIME

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

問題
HAMILTON

𝑛 の多項式時間で判定する方法が存在［AKS04］与えられたグラフがハミルトン閉路をもつか判定（全頂点を一度づつ通る辿り方）

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

613

定義
機械 𝑀 が多項式空間であるとは 或る多項式 𝑝 が存在し任意の長さ 𝑛 の任意の入力に対する 𝑀 の計算が空間 𝑝 𝑛 以内である（テープ上で初めの欄の左右 𝑝 𝑛 個の範囲に留まる）ことをいう
言語 𝐴 を認識する多項式空間の機械 𝑀 が存在するとき𝐴 は多項式空間認識可能であるという
入力長 𝑛 のとき 2𝑝 𝑛 時間以内
定理
多項式時間認識可能 ⟹ 多項式空間認識可能 ⟹ 指数時間認識可能①②① 空間を 1 使う（新たな欄に移動する）にも時間 1 かかるので

始② 多項式空間機械 𝑀 に対して多項式 𝑞 が存在し長さ 𝑛 の入力に対する 𝑀 の状況としてあり得るものは 2𝑞 𝑛 個以内受理するのであれば時間 ≤ 2𝑞 𝑛 で受理する

受状況間の遷移関係713

問題

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

PRIME

答

問題

入力 グラフ 𝐺

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

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

入力48581583386419 ÷
𝑛桁2= 24290791693209 あまり 1

3= 16193861128806 あまり 1⋮6306457

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

813

問題

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

PRIME

答

問題

入力 グラフ 𝐺

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

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

12

3456

𝑛 頂点

123456

ダメ（3と4の間や6と1の間が繫がっていないので）123465ダメ（3と4の間や4と6の間が繫がっていないので）123546⋮654321経路の候補 𝑛! 個（前指同の数
じ行的場をに所覚多にえく上ての書お手きく間
し必がて要かよはかいなる）いが

813

問題

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

SR答

問題
SR≥問題
SR1
≥

問題
SR1>

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

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

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

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

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

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

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

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

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

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

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

やがて ε に達する

容易
そう（特殊な入力）

913

問題

入力𝑅, 𝑤SR答

𝑤 ⇒∗𝑅 ε か問題
SR≥

SR を各規則が(旧長さ) ≥ (新長さ)の場合に制限したもの
SR≥ を更に問題 可能な書換え方が毎回一通り
1SR≥

な場合に制限したもの

問題

SR1≥ を更に各規則がSR1>(旧長さ) > (新長さ)の場合に制限したもの定理（昨日）SR は認識可能（だが判定可能でない）? （次頁）定理
SR1≥ は多項式空間認識可能定理
SR1> は多項式時間認識可能

テ書ー換
プえ上をで実）際行にっ順て次み（れ機ば械よのい

913

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

入力問題
SR≥問

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

𝑅, 𝑤 但し各規則が(旧長さ) ≥ (新長さ)𝑤 ⇒∗𝑅 ε か

入力の長さが 𝑛 である（𝑤 の長さ < 𝑛）とき𝑤 から書換えにより生じ得る文字列も長さ < 𝑛 でありその個数は < 2𝑛𝑛

したがって 𝑤 ⇒≤2ε かどうか調べればよい𝑅
書換え 2𝑛 回以内で 𝑤 から ε が得られる

しかしbabaaabbという意味

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

bbabbabb

bbabaabbbabbabbb

bbbababb

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

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

1013

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

入力問題
SR≥問

𝑅, 𝑤 但し各規則が(旧長さ) ≥ (新長さ)𝑤 ⇒∗𝑅 ε か𝑛𝑤 ⇒≤2
ε かどうか 次の関係を再帰的に用いて調べればよい
𝑅𝑥 ⇒≤2
𝑅𝑖+1

𝑦𝑥 ⇒≤1𝑅 𝑦𝑖𝑖≤2
或る 𝑧 ∈ 𝛴 <𝑛 が存在して 𝑥 ⇒≤2
𝑅 𝑧 かつ 𝑧 ⇒𝑅 𝑦𝑥 = 𝑦 または 𝑥 ⇒𝑅 𝑦■■ ⇒≤1
𝑅 ●● かつ≤1●● ⇒𝑅 ▲▲ か？

⋮⋮𝑛−1𝑤 ⇒≤2aa ⋯ aa かつ𝑅𝑛−1aa ⋯ aa ⇒≤2ε か？
𝑅■■ ⇒≤1
𝑅 ★★ かつ★★⇒≤1𝑅 ▲▲ か？

深さ 𝑛

⋮

𝑛−1𝑛𝑤 ⇒≤2ε か？
𝑅𝑤 ⇒≤2aa ⋯ ab かつ
𝑅𝑛−1aa ⋯ ab ⇒≤2ε か？
𝑅⋮≤ 2𝑛 個の場合分け（成立つものが一つでもあるか調べる）

それぞれ≤ 2𝑛 個の場合分け

⋮
今ココ

1113

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

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

SR1>

正則

SR≥
MOREA

PRIME

多項式時間
認識可能

SR1
≥

多項式空間
認識可能

HAMILTON

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

指数時間
認識可能

⋮⋯
判定可能

（時間制限なし）

SR

EVAL

認識可能

1213

まとめ第三日

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

13
13