実函数の計算理論

実函数の計算理論

河村彰星（京大）

令和4年7月27日

253

存在証明と計算

「任意の○○に対し△△が存在する」

存在の主張

「与えられた○○から△△を計算する方法がある」

計算可能性

「与えられた○○から△△を計算する容易な方法がある」

計算量

計算理論は数学的な存在定理の精密化 その対象を 離散・有限・組合せ数学だけでなく

様々な数学的対象に広げよう

353

例えば 実函数の計算可能性は……

決まる 連続

計算できる 計算可能

たやすく計算できる FP（多項式時間

計算可能）など

入力（精度𝛿）から 出力（精度𝜀）が

453

数値計算の基礎理論として

アルゴリズムを記述する その正しさを議論する

計算量を測る 𝑎 = 77617.0, 𝑏 = 33096.0 のとき

333.75 − 𝑎² 𝑏⁶ + 11𝑎²𝑏² − 121𝑏⁴ − 2 𝑎² + 5.5𝑏⁸ + ^𝑎

2𝑏 は？

32ビット浮動小数点演算による解 1.172604 …

64ビット浮動小数点演算による解 1.1726039400531786 …

実数そのものを扱うかのごとく記述されたアルゴリズムにおいて

代りに有限な近似値

を使ったときの正しさは判らない 本物の実数の計算を扱うには？

真の解 −0.8273960599468213 … S. Rump’s example

553

「計算可能解析学」（Computable Analysis）

V. Brattka and P. Hertling, Eds., Handbook of Computability

and Complexity in Analysis, Springer, 2021

K. Weihrauch, Computable Analysis, Springer, 2000.

http://cca-net.de/

Computability and Complexity in Analysis

Workshop（1995年～）

Conference（2005年～）

実数（など解析学的対象）を含む数学に関する計算理論

関連分野 構成的数学、逆数学、……

精度保証つき数値計算

53

 有理数や代数的数は（桁数の）多項式時間で計算可能

6

実数とは？

 デーデキント切断

0 3.1

00 3.15 000 3.141 0000 3.1416 00000 3.14159

この函数が（効率的に）計算可能であるとき 𝑡 は（効率的に）計算可能であるという

 𝜋 や e など知られた数はたいてい多項式時間で計算可能

（もちろん「殆どの」実数は計算不可能だが）

文字列 0

実数 𝑡

𝑡 の 𝑛 桁近似

コーシー列による実数の表現

（𝑡 から距離 10^−𝑛 以内にある、

小数点以下 𝑛 桁の有理数）

二つくらいある

753

実数を入出力とする函数が計算可能であるとは？

実数を入力とする函数など

函数 TRIPLE: 𝐑 → 𝐑 を

𝑥 の 𝑛 桁近似

機械 𝑀

𝑚 3 ⋅ 𝑥 の 𝑚 桁近似

以下で述べる計算可能性の枠組は Type-2 Theory of Effectivity

（二型の計算理論）と呼ばれる

神託

実数など 整数など

文字列の函数で表現（Type 1）

文字列で表現（Type 0）

Type 2 の計算

𝑛

実数 𝑥 計算する機械 𝑀

𝑥 ↦ 3 ⋅ 𝑥 例

𝑛 = 𝑚 + 2 として

質問する 得られた有理数を

3 倍して答える

計算可能 ⟹ 連続

53

計算可能 ⟹ 連続 ∴ 実数どうしの比較はできない

𝑥 ≥ 0 か判定する 函数は連続でない

（ので計算不能）

「 𝑥 < 𝜀 ではどちらを 答えてもよい」とした

多価函数も計算可能 _𝜀

𝑥 = 0 において発散する 部分函数なら計算可能

𝑥 ≥ 0

𝑥 ≳ 0

−𝜀

部分函数や多価函数を考える必要が（一型計算でも元々あるにはあるが）自然に出て来る ₈

1. 問題

53

定義

集合 𝑋 から 𝑌 への問題（ 𝑋, 𝑌 問題）𝐴 は

 集合 dom 𝐴 ⊆ 𝑋

 各 𝑥 ∈ dom 𝐴 に対して集合 𝐴 𝑥 ⊆ 𝑌 で指定される（多価部分函数） _{正解の集合} 各 𝐴 𝑥 が一点 𝐴 𝑥 からなる

dom 𝐴 = 𝑋

一価な問題（部分函数）

全域な問題

この両方 函数

dom 𝐴 ⊇ dom 𝐵 かつ

各 𝑥 ∈ dom 𝐵 で 𝐴 𝑥 ⊆ 𝐵 𝑥

定義

⟺

(𝑋, 𝑌) 問題 𝐵 が 𝐴 の鈍化

dom 𝐴 に属しない入力に 対する動作は不問

問題 𝐴 と 𝐵 を合成した問題 𝐴 ∘ 𝐵 とは

dom(𝐴 ∘ 𝐵) = 𝑥 ∈ dom 𝐵 ∶ 𝐵 𝑥 ⊆ dom 𝐴 𝐴 ∘ 𝐵 𝑥 = ራ

𝑦∈𝐵 𝑥

𝐴 𝑦 ₁₀

𝐴: ⊆ 𝑋 ⇉ 𝑌

1153

定義

位相空間 𝑋 から 𝑌 への問題 𝐴 が 強連続 であるとは任意の開集合 𝑉 ⊆ 𝑌 の逆像 𝐴⁻¹𝑉 = 𝑥 ∈ dom 𝐴 ∶ 𝐴 𝑥 ∩ 𝑉 ≠ ∅

が dom 𝐴 において開であること

問題が 連続 であるとは 強連続な問題の鈍化であること

𝜀

−𝜀 ^𝑥

𝑦

𝑓 𝑥 ∋ 𝑦

この 𝐑, 𝐑 問題 𝑓 は強連続

2. 文字列函数の計算

53

𝐹 𝐴

𝛴

𝑌 𝑋

𝛴

𝛾 𝛿

𝛴

𝛴

一般に 表現 𝛾: ⊆ 𝛴^∗∗ → 𝑋 と 𝛿: ⊆ 𝛴^∗∗ → 𝑌 の下で問題 𝐴: ⊆ 𝑋 ⇉ 𝑌 を解くとは

先程は 𝑋 = 𝑌 = 𝐑

（符号化法）

表現

𝜑 は 𝛾 𝜑 の名

𝛴

→ 𝛴

型の 函数の集合

「𝐴 を計算する」の意味は

 𝐹: ⊆ 𝛴

→ 𝛴

を計算するとは

 表現 𝛾, 𝛿 として何を使うか を決めると定まる

任意の𝜑 ∈ dom 𝐴 ∘ 𝛾 に対して 𝛿 𝐹 𝜑 ∈ 𝐴 𝛾 𝜑

（左辺が定義されて）

13

1453

神託チューリング機械（二型機械）

０００１１０１１０１１ 主テープ

計算結果

𝑀

𝑥 = 𝑦

神託テープ

１００１０１

機械 𝑀

質問 𝑞 を書き神託𝜑 に 投げかけると

次の瞬間には𝜑 𝑞 が 書かれている

定義2.1

 一型機械 𝑀 が 𝛴^∗, 𝛴^∗ 問題 𝐹 を解くとは

任意の 𝑥 ∈ dom 𝐹 に対して或る 𝑦 ∈ 𝐹 𝑥 が存在して 𝑀 𝑥 = 𝑦

 二型機械 𝑀 が 𝛴^∗∗, 𝛴^∗∗ 問題 𝐹 を解くとは

任意の 𝜑 ∈ dom 𝐹 に対して或る 𝜓 ∈ 𝐹 𝜑 が存在して 任意の 𝑢 ∈ 𝛴^∗ に対して 𝑀^𝜑 𝑢 = 𝜓 𝑢

神託𝜑 と文字列 𝑥 を与えると 停止して文字列𝑦 を書き出す

1553

二型計算における計算量

定義2.2［KC96 / KC12］

 函数 𝜑: 𝛴^∗ → 𝛴^∗ のうち 𝑥 ≤ 𝑦 ⇒ |𝜑 𝑥 | ≤ |𝜑 𝑦 | なるもの全体を 𝛴^∗∗ で表す

 そのような 𝜑 ∈ 𝛴^∗∗ の長さ 𝜑 : 𝐍 → 𝐍 を 𝜑 𝑥 = 𝜑 𝑥 で定義する

 神託チューリング機械 𝑀 が 多項式時間 とは計算 𝑀^𝜑(𝑥) における遷移回数が 或る二階多項式 𝑃(|𝜑|)(|𝑥|) で抑えられること

+ と × と |𝜑| の適用で作られる式 例えば 𝜑 4 𝜑 2 𝑥 ^{3 2} + 5 + 𝜑 𝑥 ⁴

神託 𝜑

機械 𝑀

しかしこの状況で「入力長に関する多項式時間」とは？

𝜑: 𝛴^∗ → 𝛴^∗ を機械に入力する ＝ 神託 𝜑 に質問ができる

機械に入って来る 文字列

［KC96］ B. M. Kapron and S. A. Cook. A new characterization of type-2 feasibility. SIAM J. Computing 25(1):117–132, 1996.

［KC12］ A. Kawamura and S. Cook. Complexity theory for operators in analysis. ACM Transactions on Computation Theory 4, Article 5, 2012.

𝑃: 𝐍 → 𝐍 → 𝐍 → 𝐍

一型の多項式時間を保つ 多項式空間も同様に定義

ここからは

1653

計算量の階層

FP FPSPACE Computable

多項式時間の一型機械で 解かれる 𝛴^∗, 𝛴^∗ 問題全体

多項式時間の二型機械で 解かれる 𝛴^∗∗, 𝛴^∗∗ 問題全体

FP FPSPACE Computable Continuous

⊆ ⊆

⊆

⊆ ⊆

多項式空間の一型機械で 解かれる 𝛴^∗, 𝛴^∗ 問題全体

多項式空間の二型機械で 解かれる 𝛴^∗∗, 𝛴^∗∗ 問題全体

一型機械（制限なし）で 解かれる 𝛴^∗, 𝛴^∗ 問題全体

二型機械（制限なし）で

解かれる 𝛴^∗∗, 𝛴^∗∗ 問題全体 連続（次頁）な 𝛴^∗∗, 𝛴^∗∗ 問題全体

計算結果の文字列が 1（受理）か 0（拒否）であるときのみを考えて FP やFP の代りに P やP を論ずることも多いが 今日はそうしない

（P は 𝛴^∗∗, 𝛴_0,1^∗∗ 問題の集合ということになり 少し面倒なので）

𝛴^∗, 0, 1 函数全体 一型

二型

1753

𝛴^∗∗, 𝛴^∗∗ 問題 𝐹 は 連続 ⟺ 或る機械により或る神託 𝜃 の下で解かれる 定理2.4

𝜑

𝑣 𝜑(𝑣) 機械 𝑀

𝑢 𝐹 𝜑 𝑢

𝜃

入力 𝜑 とは別に 神託 𝜃 にも

質問できる

位相空間 𝛴^{∗∗ 𝜑 ∈ 𝛴∗∗ ∶ 𝜑 𝑢 = 𝑣} という形の集合（の有限個の共通部分）が基本開集合

連続 ＝ 「出力についての有限情報は 入力についての有限情報から決まる」

3. 表現と計算

53

「𝐴 を計算する」の意味は

 𝐹: ⊆ 𝛴

→ 𝛴

を計算するとは

 表現 𝛾, 𝛿 として何を使うか を決めると定まる

✔

𝐹 𝐴

𝛴

𝑌 𝑋

𝛴

𝛾 𝛿

一般に 表現 𝛾: ⊆ 𝛴^∗∗ → 𝑋 と 𝛿: ⊆ 𝛴^∗∗ → 𝑌 の下で問題 𝐴: ⊆ 𝑋 ⇉ 𝑌 を解くとは

（符号化法）

定義（問3.1）

上図の状況（𝐴 ∘ 𝛾 が 𝛿 ∘ 𝐹 の鈍化）を「𝐹 は 𝐴 の 𝛾, 𝛿 実現である」という C に属する 𝛾, 𝛿 実現をもつ問題の全体を 𝛾, 𝛿 -C で表す

表現

𝜑 は 𝛾 𝜑 の 𝛾 名 ^任意の𝛿 𝐹 𝜑^{𝜑 ∈ dom 𝛾}= 𝐴 𝛾 𝜑^に対して

（左辺が定義されて）

19

53

定義

 文字列函数 𝜑 ∈ 𝛴^∗∗ が実数 𝑡 ∈ 𝐑 の 𝜌_C 名であるとは 各 𝜑(0^𝑛) が 𝑡 の 𝑛 桁近似（有理数）であること

函数 𝑓: ⊆ 𝐑 → 𝐑 を

𝑥 の 𝑛 桁近似

機械 𝑀

0^𝑚 𝑓 𝑥 の

𝑚 桁近似

神託

0^𝑛

実数 𝑥

計算する機械 𝑀 例

任意の 𝑥 ∈ 0, 1 は

長さ 𝜑 : 𝑛 ↦ 2𝑛 + 4 程度の 𝜌_C 名をもつ

そのような短い名に対しては計算時間 𝑃 𝑛 ↦ 2𝑛 + 4 すなわち 𝑚 のみの多項式時間で 𝑓 𝑥 を 𝑚 桁近似できる

20 二進法の分数で表す

例：”-101/1000”= ⁵

8

もし 𝑓 ∈ 𝜌_C, 𝜌_C -FP（計算時間が二階多項式 𝑃）なら

𝑓 ∈ C 0, 1 の計算では

dom 𝑓 = 0, 1 なる連続な 実数値函数

𝑓 は多項式の 連続度 𝜇: 𝐍 → 𝐍 をもつ 𝑡 − 𝑡^′ < 2^{−𝜇 𝑚}

⇒ 𝑓 𝑡 − 𝑓 𝑡^′ < 2^−𝑚

53

例 加算 +: 0, 1 ² → 𝐑 は 𝜌_C, 𝜌_C -FP

0^𝑛 𝑠 の

𝑛 桁近似

機械

0^𝑚 𝑠 + 𝑡 の

𝑚 桁近似

0^𝑛′ 𝑡 の

𝑛^′ 桁近似

sin 𝑡 = 𝑡

1!− 𝑡³

3! + 𝑡⁵

5! − 𝑡⁷

7! + ⋯

∵ sin の傾きは 1 以下

（sin 𝑡 を求めるには

近くの 𝑡^′ での値 sin 𝑡^′ を求めれば良い）

この級数の収束は十分早い

（𝑚 桁近似を得るには

初めの O 𝑚 項だけ見れば十分）

その項までの和は多項式時間で 求まる（有理数の加算・乗算）

sin: 0, 1 → 𝐑 は 𝜌_C, 𝜌_C -FP

𝑛 = 𝑛^′ = 𝑚 + 2 とすればよい

例

21

53

コーシー列表現 𝜌

を使ったが 代りに……

「単なる収束列」 ではダメ

「普通の小数展開」 もダメ 実数 𝑡

文字列 0^𝑛 有理数 𝑡_𝑛 但し lim

𝑛→∞𝑡_𝑛 = 𝑡

有限個の 𝑡_𝑛 を見ても 𝑡 に関する情報が何も得られない

実数 𝑡

文字列 0^𝑛 𝑡 の 𝑛 桁近似

（＝𝑡から距離10^−𝑛以内にある、

小数点以下𝑛桁の有理数）

𝑡 を小数点以下𝑛 桁に 切捨てたもの

簡単な函数（例えば「3 倍する」）が計算不能になってしまう

0^𝑛 𝑡 の 2^−𝑛 近似

機械 𝑀

0^𝑚 3 ⋅ 𝑡 の 2^−𝑚 近似

𝑡 = 1

3 = 0.33333333333333 …

𝑚 = 0 1以上？未満？

22

53

𝑓 ∈ C 0, 1 が 𝜌_C, 𝜌_C -FP に属する ⟺

 𝑓 は多項式の連続度をもつ

 𝜑 ∈ FP が存在し 任意の有理数 𝑢 と 𝑛 ∈ 𝐍 に対し 𝜑 𝑢, 0^𝑛 − 𝑓 𝑢 < 2^−𝑛 定理3.4

1

yes

(𝑢, 𝑣)

no

?

 below_𝑓 ∈ FP が存在し

𝑣 − 𝑓 𝑢 > 2^−𝑛 なる任意の有理数 𝑢, 𝑣 と 𝑛 ∈ 𝐍 に対し below_𝑓 𝑢, 𝑣, 0^𝑛 = 1 ⟺ 𝑣 < 𝑓 𝑢

二つめは次のように書き換えても良い

有理数での値の近似値が 多項式時間で求まる

「与えられた点 (𝑢, 𝑣) がグラフの下か上か判定せよ 但しグラフの上下2^−𝑛 以内のときは間違えてもよい」

という問題が多項式時間で解ける

𝜌

, 𝜌

-FP を神託が出て来ない形で言い換えると……

23

53

函数 𝑓 ∈ C[0, 1] の 𝛿

名とは

𝑓(𝑢) の 2

近似 (𝑢, 0

)

0

0

𝜇 は 𝑓 の連続度

連続実函数の表現

𝑢は有理数

24

前頁の定理3.4により もし 𝑓 ∈ 𝜌_C, 𝜌_C -FP であれば 𝑓 は FP の 𝛿_C 名をもつが それ以外の 𝑓 ∈ C 0, 1 も何らかの 𝛿_C 名はもつ

函数適用 APPLY: C 0, 1 × 0, 1 → 𝐑 は 𝛿_C, 𝜌_C , 𝜌_C -FP に属する 定理（問3.7）

𝜌

や 𝛿

の下での計算の例 →演習問題

53

定義

𝛾 ≤

𝛾

（id ∈ 𝛾, 𝛾^′ -𝐂）

表現 𝛾, 𝛾^′: ⊆ 𝛴^∗∗ → 𝑋 について

𝛾 は 𝛾^′ よりも強い

（豊かな情報をもつ）

𝛾 ≤

𝛾

id

𝛴

𝑋 𝑋

𝛴

𝛾 𝛾

𝛿

≤

𝛿 id

𝛴

𝑌 𝑌

𝛴

𝛿

𝛿

𝐴

𝐴 ∈ 𝛾

, 𝛿

-𝐂 𝐴 ∈ 𝛾, 𝛿 -𝐂

25 定義

⟺

⟺

𝛾 ≡_𝐂 𝛾^′

𝛾 ≤_𝐂 𝛾^′ かつ 𝛾 ≥_𝐂 𝛾^′

53

𝛾 と 𝛿 が適格なら 𝛾, 𝛿 -Continuous は連続性と同値 定理［KW85］

［KW85］C. Kreitz and K. Weihrauch. Theory of representations. Theoretical Computer Science 38, 35–53, 1985.

定義

位相空間 𝑋 の表現 𝛾: ⊆ 𝛴^∗∗ → 𝑋 が 適格（admissible）であるとは

連続性 最弱性

𝛾 は連続

𝑋 の任意の連続な表現 𝛾^′ について 𝛾^′ ≤ 𝛾

𝐑 の通常の位相の下で 例

 コーシー列表現 適格

 「普通の小数展開」 適格でない ∵ 最弱でない（𝜌_C から翻訳できない）ので

 「単なる収束列」 適格でない ∵ 不連続なので

26

𝛿_C は 函数適用 ^APPLY が 𝛿_C, 𝜌_C , 𝜌_C -FP に属するような最弱の表現法である 定理3.15

 これにリプシッツ定数の情報を付加したCL 0, 1 の表現 𝛿_CL

 導函数の情報を付加した C¹ 0, 1 の表現 𝛿_C¹ ……など それぞれの函数空間に合った表現を用いる

4. 帰着と完全問題

53

定義4.1

 𝐴, 𝐵 を 𝛴^∗, 𝛴^∗ 問題とする．

𝐴 が 𝐵 に多項式時間帰着するとは，函数 𝑟, 𝑠 ∈ FP が存在し，

任意の 𝑢 ∈ dom 𝐴 に対して 𝑠 𝑢 ∈ dom 𝐵 となり

任意の 𝑤 ∈ 𝐵 𝑠 𝑢 について 𝑟 𝑢, 𝑤 ∈ 𝐴 𝑢 となることをいう．

𝐵 を 解く

𝑠 𝑢 入力 𝑠 𝑢 に対する 𝐵 の答 𝑤

𝑢 入力 𝑢 に対する 𝐴 の答

𝐴 を 解く

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

𝐴 ≤ ^FP 𝐵

「𝐵 が解けたら𝐴 も解ける」を成立たすには

必ずしも問題 𝐴 の入力 𝑢 を問題𝐵 の入力 𝑠 𝑢 に対応させるという上記の形でなくてもよい

（例えば 𝑢 ∈ 𝐴かどうか知るために幾つかの文字列 𝑣₁, 𝑣₂, …が𝐵 に属するか否かを使うとか）

他にも「帰着」の変種はある

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

変換器

𝑠

変換器

𝑟

28

一型

推移的

53

二型計算における帰着

𝐴 ≤

𝐵 （二型問題の間の帰着）

多項式時間

𝐴

多項式時間

𝐵

答 質問

出力 入力

𝐴

答 質問

出力 入力

𝐵

［KC12］ A. Kawamura and S. Cook. Complexity theory for operators in analysis. ACM Transactions on Computation Theory 4,

Article 5, 2012. 29

53

定義4.1（続）

 𝐴, 𝐵 を 𝛴^∗∗, 𝛴^∗∗ 問題とする．

𝐴 が 𝐵 に多項式時間帰着するとは，函数 𝑟, 𝑠 ∈ FP が存在し，

任意の 𝜑 ∈ dom 𝐴 に対して 𝑠 𝜑 ∈ dom 𝐵 となり

任意の 𝜃 ∈ 𝐵 𝑠 𝜑 について 𝑟 𝜑, 𝜃 ∈ 𝐴 𝑢 となることをいう．

𝐴 ≤ ^𝐅𝐏 𝐵

変換器 𝑟

𝐴

変換器 𝑠

𝜑

𝐵

このとき もし 𝐵 ∈ 𝐂 ならば 𝐴 ∈ 𝐂

（𝐂 = FP,FPSPACE,Computable, …）

定理4.2

30

二型

53

定義

問題 𝐵 が FPSPACE 困難であるとは

任意の 𝐴 ∈ FPSPACE が 𝐵 に多項式時間帰着する（𝐴 ≤

𝐵）ことをいう さらに 𝐵 自身が FPSPACE に属するなら 𝐵 は FPSPACE 完全であるという

FPSPACE 完全な問題 𝐵

≤^𝐅𝐏

≤^𝐅𝐏

≤^𝐅𝐏

「𝐵 は FPSPACE の問題のうち最難」

FP

FPSPACE

5

「FPSPACE に属するとは 複雑さが問題 𝐵 以下であること」

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

31

53

問題

機械 𝑀 に入力 𝑥 を与えたときの出力

（空間 𝑠 以下で計算が終った場合）

入力 答

SPACE は FPSPACE 完全 定理

問題 𝐴 ∈ FPSPACE を考える

𝐴 を解く多項式空間の機械 𝑀 が存在 多項式 𝑝 が存在し

任意の長さ 𝑛 の入力 𝑥 に対して 𝑀 は空間 ≤ 𝑝 𝑛 で停止する

➡ 𝐴 𝑥 を知るには

𝑀, 𝑥, 0

を調べればよい

∵

326 一型

53

問題

QBF

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

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

∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧

∨ ∨ ∨ ∨

∧ ∧

∨

∃𝑋

. ∀𝑋

. ∃𝑋

. ∀𝑋

. 𝑋

∨ ¬𝑋

∧ 𝑋

∨ 𝑋

𝑄

𝑋

. 𝑄

𝑋

… 𝑄

𝑋

. 𝜑 𝑋

, … , 𝑋

の真偽を判定せよ

𝜑 𝑋₁, 𝑋₂, 𝑋₃, 𝑋₄

量化子 (∀ か ∃) 命題変数

真 (1) か偽 (0) の値をとる

𝜑 𝑋₁, 𝑋₂, 𝑋₃, 𝑋₄

∀𝑋₁. 𝜑 𝑋₁, 𝑋₂, 𝑋₃, 𝑋₄

∃𝑋₂. ∀𝑋₁. 𝜑 𝑋₁, 𝑋₂, 𝑋₃, 𝑋₄

∀𝑋₃. ∃𝑋₂. ∀𝑋₁. 𝜑 𝑋₁, 𝑋₂, 𝑋₃, 𝑋₄

∃𝑋₄. ∀𝑋₃. ∃𝑋₂. ∀𝑋₁. 𝜑 𝑋₁, 𝑋₂, 𝑋₃, 𝑋₄

𝑋₄ 𝑋₃ 𝑋₂ 𝑋₁

例

深さ優先探索で解ける

QBF ∀𝑥. 𝜓 𝑥

= QBF 𝜓 0 ∧ QBF 𝜓 1

深 さ 𝑛

QBF ∃𝑥. 𝜓 𝑥

= QBF 𝜓 0 ∨ QBF 𝜓 1

葉 2

枚

容易に計算できる

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 1 0 1

0 1

0 1 0 1 0 1 0 1

各葉の値は

𝜑 0, 0, 1, 0 = 偽 ^{この例では}

𝑛 = 4

QBF

は FPSPACE 完全 定理

33

3453

問題

SPACE²

組 𝑀, 𝜇, 𝜑 𝑢

与えられる神託 与えられる文字列

問題

QBF²

𝑝: 0, 1

→ 0, 1

□ に 𝑝 を代入したときの真偽

命題論理式部分に空欄□が現れる

例 ∀𝑋₂. ∃𝑋₁.□(𝑋₁) ∨ ¬𝑋₂∧□ 𝑋₂, ¬𝑋₁

機械 𝑀

函数 𝜇: 𝐍 → 𝐍（函数0^𝑛 ↦ 0^{𝜇 𝑛} で表す）

函数 𝜑 ∈ 𝛴^∗∗

答 機械 𝑀 に神託 𝜑 と入力 𝑢 を与えたときの出力

（空間 𝜇 𝑢 以下で計算が終った場合）

与えられる神託 与えられる文字列

答

穴あき量化命題論理式

これらの問題は FPSPACE 完全 定理4.3

問題

POW²

長さを保つ函数 𝑓: 𝛴^∗ → 𝛴^∗（ 𝑓 𝑥 = 𝑥 ） 𝑢

与えられる神託 与えられる文字列

答 𝑓^2𝑢 𝑢 二型

3553

定義4.5

次の問題は FPNP 完全（というのをここでは FPNP の定義とする）

問題

NTIME²

組 𝑀, 𝜇, 𝜑 𝑢

与えられる神託 与えられる文字列

問題

SAT²

𝑝: 0, 1 ^∗ → 0, 1

□ に 𝑝 を代入したときに充足可能かどうか 機械 𝑀

函数 𝜇: 𝐍 → 𝐍^{（函数0𝑛↦ 0𝜇 𝑛 で表す）}

函数 𝜑 ∈ 𝛴^∗∗

答 機械 𝑀 に神託 𝜑 と入力 𝑢, 𝑣 を与えたとき

時間 𝜇 𝑢 以下で受理するような文字列 𝑣 があるかどうか

与えられる神託 与えられる文字列

答

穴あき命題論理式

問題

EXIST²

𝑝: 𝛴^∗ → 0, 1 𝑢, 0^𝑛

与えられる神託 与えられる文字列

答 𝑝 𝑢, 𝑣 = 1 なる 𝑣 ∈ 𝛴^𝑛 があるかどうか

3653

函数 𝑔 ∈ C 0, 1

に対し ℎ =

𝑔 ∈ C 0, 1 を次で定める ℎ 𝑦 = max

𝑥∈[0,1]

𝑔 𝑥, 𝑦

C 0, 1 ² , C 0, 1 函数 MAX は 𝛿_C^′, 𝛿_C -FPNP 完全

定理4.6 𝛿_C⁻¹ ∘ ^MAX ∘ 𝛿_C^′ が 𝐅𝐏^𝐍𝐏 完全

ℎ

𝑦

最大をとる

𝑥 𝑦

𝑔

𝑦

53

ℎ

𝑦

最大をとる

𝑥 𝑦

𝑔

［Fri84］H. Friedman. The computational complexity of maximization and integration. Adv. Math. 53, 1984.

⟸ の証明の概略

系4.7［Fri84］

⟺ P = NP もし 𝑔 ∈ 𝜌_C², 𝜌_C -FP

ならば ℎ ∈ 𝜌_C, 𝜌_C -FP

「𝑔 𝑥, 𝑦 > 𝑧 か？」を

精度 2^−𝑛 で判定 「ℎ 𝑦 > 𝑧 か？」を 精度 2^−𝑛 で判定

「𝑔 𝑥, 𝑦 > 𝑧 なる 𝑥 が 存在するか？」を

精度 2^−𝑛 で判定

ℎ 𝑦 = max

𝑥∈[0,1]𝑔 𝑥, 𝑦

𝑔 ∈ 𝜌_C², 𝜌_C -𝐅𝐏 ℎ ∈ 𝜌_C, 𝜌_C -𝐅𝐏 P = NP ならば

多項式の連続度 𝑝 をもつ

2^{−𝑝 𝑛+2} の 倍数 𝑥 が

2^{− 𝑛+2}

37 (𝑔: 0, 1 ² → 𝐑)

53

ℎ

𝑦

𝜑 𝜑

𝜑

命 題

論 理 式

2^{O 𝑛} 個の割当それぞれ

での𝜑_𝑛 の値 𝑔 𝑥, 𝑦 の値：

「真」 の所には山を作る

「偽」 の所は平らにする 偽偽真偽偽偽偽偽偽偽真偽

最大をとる

𝜑

を充足する 割当の有無

𝑥 𝑦

𝑔

［Fri84］H. Friedman. The computational complexity of maximization and integration. Adv. Math. 53, 1984.

⟹ の証明の概略 「最大値を取ることができると SATが解けてしまう」

𝜑

系4.7［Fri84］

⟺ P = NP もし 𝑔 ∈ 𝜌_C², 𝜌_C -FP

ならば ℎ ∈ 𝜌_C, 𝜌_C -FP

38

ℎ 𝑦 = max

𝑥∈[0,1]𝑔 𝑥, 𝑦 ^{(𝑔: 0, 1 2} → 𝐑)

53

系［Ko83 / K10］

微分方程式の計算量

［Ko83］ K. Ko. On the computational complexity of ordinary differential equations. Inform. Contr. 58, 1983.

［K10］ A. Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. Comput. Complexity 19, 2010.

ただ一つ存在

（コーシー・リプシッツの定理）

⟺ P = PSPACE もしリプシッツ連続な 𝑔: 0, 1 ² → 𝐑 が 𝜌_C², 𝜌_C -FP ならば

ℎ 0 = 0, ℎ^′ 𝑡 = 𝑔 𝑡, ℎ 𝑡 なる ℎ: [0, 1] → 𝐑 も 𝜌_C, 𝜌_C -FP

𝑡 𝑦

0 1

𝑔(𝑡, 𝑦) ℎ(𝑡)

系

この CL 0,1 ² , C 0, 1 部分函数 𝑔 ↦ ℎ は 𝛿_CL^′ , 𝛿_C -FPSPACE 完全 定理4.8

リプシッツ連続な 函数の全体

39

53

微分方程式の解の存在と計算量

コーシー・ペアノの定理（の不 成立）＠計算可能性［PR79］

𝑔 ↦ ℎ は表現 𝛿_C の下で 計算不可能

［PR79］ M. B. Pour-El and I. Richards. A computable ordinary differential equation which possesses no computable solution. Ann.

Math. Log. 17, 1979.

ℎ 0 = 0, ℎ′(𝑡) = 𝑔(𝑡, ℎ(𝑡))

コーシー・ペアノの定理 任意の 𝑔 に対し解 ℎ は

（原点の近くで）存在

コーシー・リプシッツの定理

＠PSPACE

𝑔 ↦ ℎ は表現 𝛿_CL の下で FPSPACE

コーシー・リプシッツの定理 リプシッツ連続な 𝑔 に対し 解 ℎ が存在

コーシー・コワレフスカヤの定理

＠P

𝑔 ↦ ℎ は表現 𝛿_analytic の 下で FP

コーシー・コワレフスカヤの定理 解析的な 𝑔 に対し

解析的な解 ℎ が存在

様々な数学的現象の

データ操作としての側面を理解

数値計算の問題の難しさを 計算量により分類

40