第四日
帰着と完全問題

15

まとめ

第三日

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

15

問題の難しさを証明できる？
問題
算法１

算法２

多項式時間
認識可能

算法３

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

問題□□は容易に解けるか？
効率の良い算法（＝機械）が存在するか？

「問題□□は如何なる算法を以てしても（時間△△では）解けない」という証明をすることは難しく なかなか成功していない……

115

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

多項式時間
認識可能
HAMILTON

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

SR1
≥

多項式空間
認識可能

多項式時間認識可能かどうか不明な重要問題は多い
それでも問題の間の帰着関係によって困難さを比べたりそれにより問題が「おそらく困難」と示したりできる場合がある（以下で扱う）
215

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

𝐴 ≤P 𝐵 と書く
向きに注意「𝐴 の難しさは 𝐵 以下」という気持なのでこの不等号で表す「𝐵 を使うと 𝐴 が計算できる」

𝐵を認識

𝑇 𝑥変換器

𝑇𝑥

𝐴を認識

入力 𝑇 𝑥 に対する 𝐵 の答
（受理／不受理）

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

315

𝐴 ≤P 𝐵 であるとすると…
もし 𝐵 が多項式時間認識可能ならば 𝐴 も多項式時間認識可能
もし 𝐵 が多項式空間認識可能ならば 𝐴 も多項式空間認識可能
もし 𝐵 が 判定 可能 ならば 𝐴 も 判 定 可能

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

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

入力𝑀, 𝑥問題

入力𝑅, 𝑤

EVAL答

𝑀 は 𝑥 を受理するかSR答𝑤 ⇒∗𝑅 ε か第二日には EVAL ≤P SR を示すことでEVAL の判定不能性から SR の判定不能性を導いた（その時点では帰着が多項式時間どうかは気にしていなかったが）

415

定義
多項式空間認識可能な言語 𝐵 が多項式空間完全であるとは任意の多項式空間認識可能な言語 𝐴 が 𝐵 に多項式時間帰着する（𝐴 ≤𝐏m 𝐵）ことをいう「𝐵 は多項式空間認識可能な問題のうち最難」「多項式時間認識可能＝多項式空間認識可能でない限り𝐵 は多項式時間で解けない」「多項式空間認識可能とは 複雑さが問題 𝐵 以下であること」≤𝐏

多項式時間認識可能≤𝐏≤𝐏

多項式空間認識可能多項式空間完全な問題 𝐵
そんな特別な問題が存在するの？

515

問題 EVAL
問題 EVALspace

入力 文字列の組 𝑀, 𝑥答

機械 𝑀 は入力 𝑥 を受理するか

入力 文字列の組 𝑀, 𝑥, 0 𝑠答

機械 𝑀 は入力 𝑥 を空間 𝑠 以下で受理するか定理
EVALspace は多項式空間完全∵ 多項式空間認識可能な言語 𝐴 を考える
𝐴 を認識する多項式空間の機械 𝑀 が存在
多項式 𝑝 が存在し任意の長さ 𝑛 の入力 𝑥 に対して 𝑀 は空間 ≤ 𝑝 𝑛 で停止する
そこで 𝑇 𝑥 = 𝑀, 𝑥, 0 𝑝 𝑛とすると 𝑇 は 𝐴 から EVAL への帰着
615

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

入力
問

帰 （略）
着入力

問題
問題 EVALspace

𝑀, 𝑥, 0 𝑠

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

問

𝑅, 𝑤, 𝑤 ′′ 但し各規則が(旧長さ) ≥ (新長さ)𝑤 ⇒∗𝑅 𝑢𝑤 ′′ 𝑣 なる
文字列 𝑢, 𝑣 は存在するか受𝑅, ␣𝑠 𝑞始𝑥␣𝑠 , ⊥𝑅 は 𝑀 の各状態 𝑞 ∈ 𝑄 と文字 𝜎 ∈ 𝛤 について次の規則を加えて作る• もし 𝛿 𝑞, 𝜎 = 𝑞 ′ , 𝜎 ′ , ㊧ ならば 各 𝜏 ∈ 𝛤 に対し規則 𝜏𝑞𝜎 → 𝑞 ′ 𝜏𝜎 ′• もし 𝛿 𝑞, 𝜎 = 𝑞 ′ , 𝜎 ′ , ㊨ ならば 規則 𝑞𝜎 → 𝜎 ′ 𝑞 ′• もし 𝛿 𝑞, 𝜎 = 止 かつ 𝑞 ∈ 𝑄受理 ならば 規則 𝑞𝜎 → 受⊥（EVAL ≤P SR′′ のときに設けた「空白文字を端に付け足す規則」 ▸ → ▸␣ および ◂ → ␣◂ は設けない）

𝑀は𝑥を⟺
すると
空間 ≤ 𝑠 で受理

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

715

命題変数

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

真（1）か偽（0）の値をとる

𝑄𝑛 𝑋𝑛 . 𝑄𝑛−1 𝑋𝑛−1 … 𝑄1 𝑋1 . 𝜑 𝑋1 , … , 𝑋𝑛

QBFの真偽を判定せよ

量化子（∀ か ∃）「二人ゲームでどちらが必勝か判定する問題」

例∃𝑋4 . ∀𝑋3 . ∃𝑋2 . ∀𝑋1 . 𝑋2 ∨ ¬𝑋3 ∧ 𝑋1 ∨ 𝑋401

∧深 𝑋3
さ𝑛 𝑋2

∀𝑋3 . ∃𝑋2 . ∀𝑋1 . 𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4

∧01

∨0

∨

1

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

∧∧

∧

∧∧∧

∧

∧

𝑋1 0 10 10 10 10 10 10 10 1

偽 真 偽 真 偽 偽 偽 真 真 真 真 真 偽 偽 真 真

𝜑 0,0, 1, 0 = 偽
各葉の値は容易に計算できる

命題変数から論理記号∧（かつ）∨（または）¬（否定）を使って作られる式∃𝑋4 . ∀𝑋3 . ∃𝑋2 . ∀𝑋1 . 𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4

∨

𝑋4

命題論理式

葉 2𝑛 枚この例では𝑛=4QBF ∃𝑥. 𝜓 𝑥= QBF 𝜓 0 ∨ QBF 𝜓 1∀𝑋1 . 𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4

𝜑 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4

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

定理
QBF は多項式空間完全問題
SR≥

入力
問𝑅, 𝑤 但し各規則が(旧長さ) ≥ (新長さ)𝑤 ⇒∗𝑅 ε か𝑛PSR≥ ≤ QBF を示す𝑤 ⇒≤2ε かどうかを𝑅
調べれば良い（昨日）

昨日 SR≥ の多項式空間認識可能性を示したときと同じ次の関係を用いる
𝑖+1
𝑥 ⇒≤2𝑦𝑅<𝑛「∃ 𝑤」は「或る 𝑤 ∈ 𝛴 が存在して」
𝑖≤2𝑖∃ 𝑧 (𝑥 ⇒≤2𝑧かつ𝑧⇒𝑦)𝑅𝑅「∀ 𝑤」は「任意の 𝑤 ∈ 𝛴 <𝑛 に対し」の意∃ 𝑧 ∀ 𝑢, 𝑣𝑖
(もし 𝑢, 𝑣 = 𝑥, 𝑧 または = 𝑧, 𝑦 ならば 𝑢 ⇒≤2𝑅 𝑣)
これを再帰的に用いて𝑛∃ 𝑧𝑛 ∀ 𝑢𝑛 , 𝑣𝑛 ∃ 𝑧𝑛−1 ∀ 𝑢𝑛−1 , 𝑣𝑛−1 …… ∃ 𝑧1 ∀ 𝑢1 , 𝑣1
𝑤 ⇒≤2ε𝑅もし 𝑢𝑛 , 𝑣𝑛 = 𝑤, 𝑧𝑛 または = 𝑧𝑛 , ε ならばもし ≤2𝑢 𝑛−1 , 𝑣𝑛−1 = 𝑢𝑛 , 𝑧𝑛−1 または = 𝑧𝑛−1 , 𝑣𝑛 ならば𝑢𝑛 ⇒𝑅 𝑛−1𝑛−2𝑣…… ≤2 𝑛
これを𝑢𝑛−1 ⇒𝑅𝑣𝑛−1
量化命題論理式として もし𝑢1 , 𝑣1 = 𝑢2 , 𝑧1 または = 𝑧1 , 𝑣2 ならば 𝑢1 ⇒≤1𝑅 𝑣1 )書くことができる

915様々な分野の多項式空間完全問題
様々な到達可能性を判定する問題（文字列の書換え以外にも）二人ゲームの勝負を判定する問題（囲碁など）［LS80］
不確実さの下での最適化問題［Pap85］

有限状態機械の操作に関する問題［Koz77, JR93］
周期的なスケジューリングや配置計画を最適化する問題［Orl81］
常微分方程式の数値計算に関する問題［Kaw10］［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.

1015

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

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

SR1>

正則

QBF

MOREA

PRIME

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

NPSR≥
SR1≥

多項式
空間
完
全多項式空間
認識可能
指数時間
認識可能

⋮

指数時
間
完
全⋯
判定可能
（時間制限なし）

SR

EVAL

認識可能

1115

まとめ第四日

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

1215

クラス

様々な計算量 級

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

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

1315

クラス

様々な計算量 級「Complexity Zoology」
https://www.math.ucdavis.edu/~greg/zoology/
指数時間
認識可能（EXP）
多項式空間認識可能（PSPACE）

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

1415

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

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

1515