再まとめ

第三日

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

第四日
帰着と完全問題1515

多項式時間認識可能でなく多項式空間認識可能である問題が存在するかは未解決問題の難しさを証明できる？
問題

多項式時間
認識可能

問題□□は容易に解けるか？

SR
SR

算法１

算法２

算法３

多項式時間 多項式時間 多項式時間
でないでない……

MOREA効率の良い算法（＝機械）が存在するか？

PRIME

多項式時間
認識可能
HAMILTON「問題□□は如何なる算法を以てしても（時間△△では）解けない」という証明をすることは難しく

図では SR や SR や HAMILTON が多項式時間認識可能の外側にあるが本当にそうとは証明できていないSR

多項式空間認識可能

多項式時間認識可能かどうか不明な重要問題は多い

なかなか成功していない……

それでも問題の間の帰着関係によって困難さを比べたりそれにより問題が「おそらく困難」と示したりできる場合がある
1（以下で扱う）

15215定義𝐴 ≤ 𝐵 であるとすると…

言語 𝐴 が言語 𝐵 に多項式時間帰着するとは多項式時間機械 𝑇 が存在して停止したときの任意の入力 𝑥 に対する 𝑇 の出力 𝑇 𝑥 が テープ上の文字列𝑥 ∈ 𝐴 ⟺ 𝑇 𝑥 ∈ 𝐵 を満すことをいう

もし 𝐵 が多項式時間認識可能ならばもし 𝐵 が多項式空間認識可能ならば𝐴 も多項式時間認識可能
𝐴 も多項式空間認識可能

もし 𝐵 が判

定可能ならば𝐴も判定可能

もし 𝐵 が認識可能ならば𝐴も認識可能

𝐵を認識𝐴 ≤ 𝐵 と書く
向きに注意

問題どうしの相対的な困難さの比較ができる

入力 𝑇 𝑥 に対する 𝐵 の答

𝑇 𝑥

「𝐴 の難しさは 𝐵 以下」という気持なのでこの不等号で表す

𝐴を認識

変換器

（受理／不受理）

問題

𝑇「𝐵 を使うと 𝐴 が計算できる」

𝑥EVAL

入力 𝑥 に対する 𝐴 の答

（受理／不受理）「𝐵 が多項式時間計算可能ならば 𝐴 も然り」を成立たすには必ずしも問題 𝐴 の入力 𝑥 を問題 𝐵 の入力 𝑇 𝑥 に対応させるという上記の形でなくてもよい（例えば 𝑥 ∈ 𝐴 かどうか知るために幾つかの文字列 𝑦 , 𝑦 , …が 𝐵 に属するか否かを使うとか）つまり上記の定義は「帰着」のうち特殊な形のものである
しかし今日の話にはこの形の帰着で十分なので 以下ではこれを単に「帰着」という3

問題 EVAL

多項式空間
認識可能

𝑀 は 𝑥 を受理するか

答𝑤 ⇒∗ ε か15

入力 文字列の組 𝑀, 𝑥答

機械 𝑀 は入力 𝑥 を受理するか入力 文字列の組 𝑀, 𝑥, 0
答

機械 𝑀 は入力 𝑥 を空間 𝑠 以下で受理するか定理
EVALは多項式空間完全∵ 多項式空間認識可能な言語 𝐴 を考える
𝐴 を認識する多項式空間の機械 𝑀 が存在
多項式 𝑝 が存在し任意の⾧さ 𝑛 の入力 𝑥 に対して 𝑀 は空間 ≤ 𝑝 𝑛 で停止する

𝐏

≤𝐏

𝑅, 𝑤4

問題 EVAL

複雑さが問題 𝐵 以下であること」≤

入力SR15「𝐵 は多項式空間認識可能な問題のうち最難」「多項式時間認識可能＝多項式空間認識可能でない限り𝐵 は多項式時間で解けない」≤𝐏問題（その時点では帰着が多項式時間どうかは気にしていなかったが）多項式空間認識可能な言語 𝐵 が多項式空間完全であるとは任意の多項式空間認識可能な言語 𝐴 が 𝐵 に多項式時間帰着する（𝐴 ≤ 𝐵）ことをいう

多項式時間認識可能答

𝑀, 𝑥

第二日には EVAL ≤ SR を示すことでEVAL の判定不能性から SR の判定不能性を導いた定義「多項式空間認識可能とは入力多項式空間完全な問題 𝐵

そこで 𝑇 𝑥 = 𝑀, 𝑥, 0

そんな特別な問題が存在するの？

515とすると 𝑇 は 𝐴 から EVAL への帰着
615

定理
問題
SR は多項式空間完全 （同じ証明により SR も） SR
第二日の EVAL ≤ SR ≤ SRと同様に≤ SR ≤ SR を示す
EVAL
帰着

問

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

入力
問

𝑅 の規則に従って ␣ 𝑞始𝑥␣ からが成立
受⊥ を含む文字列に到達できるSR問題
SR

入力
問

深 𝑋
さ𝑛 𝑋
𝑋𝑦

∃ 𝑧 (𝑥 ⇒𝑧 かつ 𝑧 ⇒「∃ 𝑤」は「或る 𝑤 ∈ 𝛴

7150∧∀𝑋 . ∃𝑋 . ∀𝑋 . 𝜑 𝑋 , 𝑋 , 𝑋 , 𝑋
1∨

QBF ∀𝑥. 𝜓 𝑥= QBF 𝜓 0 ∧ QBF 𝜓 1∃𝑋 . ∀𝑋 . 𝜑 𝑋 , 𝑋 , 𝑋 , 𝑋∨01010101∧∧∧∧∧∧∧∧

0 10 10 10 10 10 10 10 1

容易に計算できる

命題変数から論理記号∧（かつ）∨（または）¬（否定）を使って作られる式

葉2 枚

この例では
𝑛=4

QBF ∃𝑥. 𝜓 𝑥= QBF 𝜓 0 ∨ QBF 𝜓 1∀𝑋 . 𝜑 𝑋 , 𝑋 , 𝑋 , 𝑋

𝜑 𝑋 ,𝑋 ,𝑋 ,𝑋

深さ優先探索多項式空間認識可能815

様々な分野の多項式空間完全問題
様々な到達可能性を判定する問題（文字列の書換え以外にも）二人ゲームの勝負を判定する問題（囲碁など）［LS80］
不確実さの下での最適化問題［Pap85］が存在して」に対し」の意有限状態機械の操作に関する問題［Koz77, JR93］∃ 𝑧 ∀ 𝑢, 𝑣
(もし 𝑢, 𝑣 = 𝑥, 𝑧 または = 𝑧, 𝑦 ならば 𝑢 ⇒ 𝑣)
これを再帰的に用いて∃ 𝑧 ∀ 𝑢 ,𝑣∃𝑧
∀ 𝑢 ,𝑣…… ∃ 𝑧 ∀ 𝑢 , 𝑣𝑤⇒
ε

これを量化命題論理式として書くことができる

1∨

𝜑 0,0, 1, 0 = 偽
各葉の値は𝑅, 𝑤 但し各規則が(旧⾧さ) ≥ (新⾧さ)𝑤 ⇒∗ ε か𝑦) 「∀ 𝑤」は「任意の 𝑤 ∈ 𝛴1

∨

命題論理式

∃𝑋 . ∀𝑋 . ∃𝑋 . ∀𝑋 . 𝜑 𝑋 , 𝑋 , 𝑋 , 𝑋0∧0

∧ 𝑋 ∨𝑋偽 真 偽 真 偽 偽 偽 真 真 真 真 真 偽 偽 真 真

昨日 SR の多項式空間認識可能性を示したときと同じ次の関係を用いる
𝑥⇒

量化子（∀ か ∃）∨𝑤⇒
ε かどうかを調べれば良い（昨日）≤ QBF を示す

…𝑄 𝑋 .𝜑 𝑋 ,…,𝑋

∃𝑋 . ∀𝑋 . ∃𝑋 . ∀𝑋 . 𝑋 ∨ ¬𝑋𝑋（EVAL ≤ SR のときに設けた「空白文字を端に付け足す規則」 ▸ → ▸␣ および ◂ → ␣◂ は設けない）

定理
QBF は多項式空間完全の真偽を判定せよ

例

𝑅 は 𝑀 の各状態 𝑞 ∈ 𝑄 と文字 𝜎 ∈ 𝛤 について次の規則を加えて作る• もし 𝛿 𝑞, 𝜎 = 𝑞 , 𝜎 , ㊧ ならば 各 𝜏 ∈ 𝛤 に対し規則 𝜏𝑞𝜎 → 𝑞 𝜏𝜎
• もし 𝛿 𝑞, 𝜎 = 𝑞 , 𝜎 , ㊨ ならば 規則 𝑞𝜎 → 𝜎 𝑞• もし 𝛿 𝑞, 𝜎 = 止 かつ 𝑞 ∈ 𝑄受理 ならば 規則 𝑞𝜎 → 受
⊥
𝑀は𝑥を⟺
すると
空間 ≤ 𝑠 で受理

𝑋真（1）か偽（0）の値をとる「二人ゲームでどちらが必勝か判定する問題」

受𝑅, ␣ 𝑞始𝑥␣ , ⊥𝑀, 𝑥, 0

𝑄 𝑋 .𝑄

QBF

𝑅, 𝑤, 𝑤 但し各規則が(旧⾧さ) ≥ (新⾧さ)𝑤 ⇒∗ 𝑢𝑤 𝑣 なる
文字列 𝑢, 𝑣 は存在するか

命題変数

与えられた量化命題論理式問題

帰 （略）
着問題
問題 EVAL入力

周期的なスケジューリングや配置計画を最適化する問題［Orl81］
常微分方程式の数値計算に関する問題［Kaw10］

もし 𝑢 , 𝑣 = 𝑤, 𝑧 または = 𝑧 , ε ならばもし 𝑢 , 𝑣= 𝑢 ,𝑧または = 𝑧 , 𝑣 ならば𝑢 ⇒𝑣……
𝑢⇒𝑣
もし 𝑢 , 𝑣 = 𝑢 , 𝑧 または = 𝑧 , 𝑣 ならば 𝑢 ⇒ 𝑣 )9［LS80］D. Lichtenstein and M. Sipser. Go is polynomial-space hard. Journal of the ACM, 27: 393–401, 1980.
［Pap85］C. H. Papadimitriou. Games against nature. Journal of Computer and System Sciences, 31: 288–301, 1985.
［Koz77］D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symposium on the Foundations ofComputer Science, 254–266, 1977.
［JR93］T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22: 1117–1141, 1993.
［Orl81］J. B. Orlin. The complexity of dynamic languages and dynamic optimization problems. In Proc. 13th ACM
Symposium on the Theory of Computing, 218–227, 1981.
［Kaw10］A. Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete.
Computational Complexity, 19: 305–332, 2010.

15

1015

NP については
本講義では触れなかった

複雑さの階層と完全問題
ABA

SR

正則

QBF

MOREA
PRIME

SAT

多項式時間
認識可能（P）
NP 完全
HAMILTON

NPSR
SR

多項式
空間
完
全まとめ

第四日

帰着と完全問題• 帰着により問題の難しさを比べる• ○○完全 ＝ 「○○なうちで最難」の問題• 多様なジャンルの○○完全問題
見た目は違えど困難さの核心は同じ• 多項式空間完全な問題「到達性の判定」「二者間のゲーム」等の要素からくる困難さ

指数
時
間完
全

多項式空間
認識可能（PSPACE）
指数時間
認識可能

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

SREVAL

認識可能

111215クラス

様々な計算量 級

15クラス

ウェブサイト「Complexity Zoo」 500以上の計算量級を紹介
https://complexityzoo.net/Complexity_Zoo

様々な計算量 級「Complexity Zoology」

本講義で扱った• 正則（REG）• 多項式時間認識可能（P）• 多項式空間認識可能（PSPACE）• 判定可能（R または Decidable）• 認識可能（RE または CE）
以外にも問題の複雑さの度合を色々な側面から捉えた基準が数多く定義され研究されている

https://www.math.ucdavis.edu/~greg/zoology/
指数時間
認識可能（EXP）
多項式空間認識可能（PSPACE）

多項式時間
認識可能（P）

1315

1415

M・シプサ著、太田・田中監訳『計算理論の基礎 原著第二版』共立出版（平成20年）

岩間一雄『アルゴリズム理論入門』朝倉書店（平成26年）

1515