脱乱択化の理論と
メタ計算量
平原 秀一

情報学プリンシプル研究系・准教授@組合せ最適化セミナー

２０２３年８月９日

概要
1. 脱乱択化の理論• 理論の概要• 疑似乱数生成器の概念• 疑似乱数生成器の構成

2. メタ計算量と平均時計算量について• メタ計算問題• 平均時計算量• 最悪時・平均時計算量の同値性• 暗号との関係

乱択アルゴリズム (Randomized algorithm)
例：モンテカルロ法、クイックソート、多項式同一性判定、…
➢ 乱択アルゴリズムは非常に有用である。しかし…
➢ どのようにして乱択アルゴリズムを実装すべきだろうか？
• srand(time(NULL)); rand(); rand(); …

← 理論的な保証なし• 時間、マウスの動き、ノイズ、放射線などを使う← デバイス依存＆一様分布とは限らない➢ 計算量理論における二つのアプローチ
1. Randomness extractor
2. Derandomization （脱乱択化）

二つのアプローチ
1. Randomness extractor• ほぼ一様ランダムな乱数列を 「十分ランダムな」乱数列から抽出する。
（「十分ランダムな」: 最小エントロピーが大きい）• 例：マウスの動きから一様ランダムな乱数列を抽出できる。

2. 脱乱択化（Derandomization）• 効率的な乱択アルゴリズムが用いる乱数の量を（理想的には）𝑂 log 𝑛 ビットまで減らす技術。
• 𝑂(log 𝑛)長の乱数列は、全探索により多項式時間で模倣できる。
• 「𝐏 = 𝐁𝐏𝐏予想」の根拠となった理論。

𝐏: Polynomial-time➢ 𝑓: 0,1 ∗ → 0,1 ： 判定問題

➢ （決定性）多項式時間アルゴリズム𝐴が𝑓を解くとは、全ての𝑛 ∈ ℕ、全ての入力𝑥 ∈ 0,1 𝑛 について、

𝐴 𝑥 = 𝑓(𝑥)𝑥: 入力が成立することをいう。

P ≔ 判定問題𝑓 ある多項式時間アルゴリズム𝐴が𝑓を解く

𝐁𝐏𝐏: Bounded-error Probabilistic Polynomial-time➢ 𝑓: 0,1 ∗ → 0,1 ： 判定問題

➢ 乱択多項式時間アルゴリズム𝐴が𝑓を解くとは、ある多項式𝑝が存在し、全ての𝑛 ∈ ℕ、全ての入力𝑥 ∈ 0,1 𝑛 について、
3
Pr 𝑝(𝑛) 𝐴 𝑥; 𝑟 = 𝑓(𝑥) ≥4𝑟∼ 0,1が成立することをいう。

𝑥: 入力
𝑟: 一様ランダムな文字列（真の乱数列）BPP ≔ 判定問題𝑓 ある乱択多項式時間アルゴリズム𝐴が𝑓を解く

Hardness versus Randomness framework
計算困難性

乱択

[Yao’82], [Blum & Micali ’84],[Nisan & Wigderson ’94], …

➢ 困難性と乱雑性は両立しない。
Theorem [Impagliazzo & Wigderson 1997]

E ⊈ io-SIZE 20.01𝑛
計算困難性（回路下界）
指数時間2𝑂(𝑛) で計算可能だが、20.01𝑛 サイズの論理回路では計算不可能な判定問題が存在するならばE ≔ DTIME 2𝑂 𝑛 .

⟹P = BPP.
脱乱択化

乱択多項式時間アルゴリズムを
決定性多項式時間アルゴリズムに変換できる。

出力ゲート回路の定義➢ 回路とは、ラベル付き有向非巡回グラフ（DAG; directed acyclic graph）であって、各頂点のラベルはAND, OR, NOTゲートまたは入力ゲート𝑥1 , … , 𝑥𝑛 か定数0, 1のいずれかのラベル付けがされているもの。
•

出次数0の頂点は出力ゲートと呼ばれる。

•

入次数：AND, ORゲートは2, NOTゲートは1,
入力ゲートと定数ゲートは0。

•

回路サイズ ≔ AND, OR, NOTゲートの個数➢ 最も基礎的かつ重要な計算モデルの一つ。
•

コンピュータを作るときにも用いられる。

∨
∧

∨

∨

¬

𝑥1

𝑥2

ANDゲート（論理積ゲート）∧: 0,1 2 → {0,1}1,𝑥∧𝑦 =ቊ
0,

𝑥=𝑦=1
otherwise

0

1

∧
1

𝑥

∧
𝑦

0

1

𝑥

𝑦

1

ORゲート（論理和ゲート）∨: 0,1 2 → {0,1}1,𝑥∨𝑦 =ቊ
0,

𝑥 = 1 or 𝑦 = 1
otherwise

1

0

∨
1

𝑥

∨
𝑦

0

0

𝑥

𝑦

0

NOTゲート（論理否定ゲート）¬: 0,1 1 → {0,1}0,¬𝑥 = ቊ
1,

𝑥=1
x=0

0

1

¬
1

𝑥

¬
0

𝑥

サイズ5の回路の例

回路の例

1

∨ 出力ゲート➢ 以下の関数𝑓: 0,1 2 → {0,1}を計算する。
𝒙𝟏 𝒙𝟐

𝒇(𝒙𝟏 , 𝒙𝟐 )

0

0

1

0

1

1

1

0

1

1

1

1

0

0
➢ 実は定数関数を計算する！
•

より小さい回路でも同じ関数が計算できる。 0

∧

∨

∨
𝑥1

¬
0

1

1

𝑥2 入力ゲート回路：非一様な計算モデル➢ （論理）回路：チューリング機械よりも組合せ論的で扱いやすい∨• 回路は有限の関数 𝑓: 0,1 𝑛 → {0,1} を計算する。
➢ 判定問題𝑓: 0,1 ∗ → {0,1}を回路族 𝐶𝑛 𝑛∈ℕ が計算する（定義）⟺ 各𝑛 ∈ ℕについて、𝐶𝑛 が𝑓𝑛 ≔ 𝑓 ȁ 0,1 𝑛 を計算する• 各𝑛について異なる回路を用いてよい（非一様性）➢ 多項式時間チューリング機械は多項式サイズの回路で模倣できる。

P ⊆ SIZE 𝑛

𝑂(1)

∧

∨

∨

¬

𝑥1

𝑥2

Hardness versus Randomness framework
計算困難性

乱択

Theorem [Impagliazzo & Wigderson 1997]

E ⊈ io-SIZE 20.01𝑛⟹

計算困難性（回路下界）

P = BPP.
脱乱択化

仮定： E = DTIME 2𝑂(𝑛) を20.01𝑛 サイズの論理回路で計算できない。
結論： 乱択多項式時間アルゴリズムを脱乱できる。

不可能性 ⟹ 可能性

Hardness versus Randomness framework
計算困難性

乱択

Theorem [Impagliazzo & Wigderson 1997]

E ⊈ io-SIZE 20.01𝑛⟹

計算困難性（回路下界）

P = BPP.
脱乱択化

仮定： 𝐄 = 𝐃𝐓𝐈𝐌𝐄 𝟐𝑶(𝒏) を20.01𝑛 サイズの論理回路で計算できない。
結論： 効率的なアルゴリズムでは「識別できない」（に対して安全な）「疑似乱数生成器」を計算できる。
不可能性 ⟹ 可能性

概要
1. 脱乱択化の理論• 理論の概要• 疑似乱数生成器の概念• 疑似乱数生成器の構成

2. メタ計算量と平均時計算量について• メタ計算問題• 平均時計算量• 最悪時・平均時計算量の同値性• 暗号との関係

rand()関数はよい疑似乱数列だろうか？
➢ 乱択アルゴリズム 𝐴 𝑥; 𝑟 を「実装」しよう。
• どのように乱数列𝑟 ∼ 0,1 ∗ を模倣すべきだろうか。
➢ rand()の実装例（線形合同法）
int rand () {rand_next = rand_next * 1103515245 + 12345;
return rand_next & 0x7fffffff;}

𝑟0 ≔ srand(time NULL )𝑟1 ≔ rand()𝑟2 ≔ rand()𝑟3 ≔ rand()…

rand()関数はよい疑似乱数列だろうか？
➢ 乱択アルゴリズム 𝐴 𝑥; 𝑟 を「実装」しよう。
• どのように乱数列𝑟 ∼ 0,1 ∗ を模倣すべきだろうか。
➢ rand()の実装例（線形合同法）
int rand () {rand_next = rand_next * 1103515245 + 12345;
return rand_next & 0x7fffffff;}

𝑟0 ≔ seed
𝑟1 ≔ 1103515245 × 𝑟0 + 12345 mod 231
𝑟2 ≔ 1103515245 × 𝑟1 + 12345 mod 231
𝑟3 ≔ 1103515245 × 𝑟2 + 12345 mod 231…

𝑟1 ∈ 0,1 31
𝑟2 ∈ 0,1 31
𝑟3 ∈ 0,1 31

𝐴 𝑥; 𝑟 をrand()関数で模倣する➢ 𝐺: 0,1 𝑠 → 0,1 31𝑚 を疑似乱数の種𝑧 ∈ 0,1 𝑠 を受け取って、rand()関数によって生成される列を出力する関数と定める。

𝐺 𝑧 ≔ 𝑟1 𝑟2 𝑟3 … 𝑟𝑚
ここで、𝑟𝑖+1 = 𝑎𝑟𝑖 + 𝑐 mod 231 , 𝑟0 = 𝑧, 𝑎 = 1103515245, 𝑐 = 12345.
➢ 以下の意味で𝐴(𝑥; 𝑟)を正しく模倣できるだろうか？
∀𝑥,

Pr 31𝑚 𝐴 𝑥; 𝑟 = 𝑓(𝑥) ≈𝑟∼ 0,1Pr𝑧∼ 0,1 𝑠

𝐴 𝑥; 𝐺 𝑧=𝑓 𝑥 .

• ここで、𝑓: 0,1 ∗ → {0,1}は𝐴によって計算される判定問題とする。

𝐴 𝑥; 𝑟 をrand()関数で模倣する➢ 𝐺: 0,1 𝑠 → 0,1 31𝑚 を疑似乱数の種𝑧 ∈ 0,1 𝑠 を受け取って、rand()関数によって生成される列を出力する関数と定める。

𝐺 𝑧 ≔ 𝑟1 𝑟2 𝑟3 … 𝑟𝑚
ここで、𝑟𝑖+1 = 𝑎𝑟𝑖 + 𝑐 mod 231 , 𝑟0 = 𝑧, 𝑎 = 1103515245, 𝑐 = 12345.
➢ 以下の意味で𝐴(𝑥; 𝑟)を正しく模倣できるだろうか？
∀𝑥,

Pr 31𝑚 𝐴 𝑥; 𝑟 = 𝟏 ≈𝑟∼ 0,1Pr𝑧∼ 0,1 𝑠

𝐴 𝑥; 𝐺 𝑧=𝟏 .

• ここで、𝑓: 0,1 ∗ → {0,1}は𝐴によって計算される判定問題とする。
• 簡単のため、𝒇 ≡ 𝟏とする。（実は回路については一般性を失わない。）

rand()はあるアルゴリズム𝐴を模倣できない➢ 𝐺: 0,1 𝑠 → 0,1 31𝑚

𝐺 𝑧 = 𝑟1 𝑟2 𝑟3 … 𝑟𝑚 , where 𝑟𝑖+1 ≔ 𝑎𝑟𝑖 + 𝑐 mod 231 , 𝑟0 ≔ 𝑧.
➢ 次のアルゴリズム𝐴 ; 𝑟 を考える： 𝐴 ; 𝑟1 𝑟2 𝑟3 … ≔ ቊ1
0

if 𝑟2 = 𝑎𝑟1 + 𝑐 mod 231
otherwise➢ すると：
Pr 31𝑚 𝐴 ; 𝑟 = 1 =𝑟∼ 0,1Pr

𝑟1 ,𝑟2 ∼ 0,1

31 = 2−31 ≈ 0.
𝑟
=
𝑎𝑟
+
𝑐
mod
2
1
31 2

≪

Pr 𝑠 𝐴 ; 𝐺 𝑧𝑧∼ 0,1➢ 𝐴(; −)は疑似乱数列𝐺(𝑧)と真の乱数列𝑟を識別できる。

= 1 = 1.

統計的検定（Statistical Test）➢ より一般に、𝐺: 0,1 𝑠 → 0,1 𝑚 を 𝑠 < 𝑚を満たす関数とする。
長さ𝑠の疑似乱数の種𝑧を受け取って、「疑似乱数列」 𝐺 𝑧 を出力する関数だとみなす。

➢ 関数𝑇: 0,1 𝑚 → {0,1}が𝐺(−)を（一様分布から）𝜖-識別する とは、Pr 𝑠 𝑇 𝐺 𝑧

𝑧∼ 0,1=1 −Pr 𝑚 𝑇 𝑟 = 1 ≥ 𝜖𝑟∼ 0,1➢ 𝑇は𝐺(−)に対する𝜖-統計的検定（または 𝜖-distinguisher）とも呼ばれる。
➢ 通常は𝜖 ≔ 1/𝑚と定義して、単純に𝑇が𝐺(−)を識別するという。

疑似乱数生成器 (PRG; Pseudorandom Generator)
定義： 疑似乱数生成器
関数𝐺: 0,1 𝑠 → 0,1 𝑚 と統計的検定のクラス𝒞について、

𝑠 < 𝑚 かつ 任意の𝑇 ∈ 𝒞が𝐺を𝜖-識別できない、つまりPr𝑧∼ 0,1 𝑠

𝑇 𝐺 𝑧

=1 −

Pr

𝑟∼ 0,1 𝑚

𝑇 𝑟 =1 <𝜖のとき、𝐺をクラス𝒞に対して𝝐-安全な疑似乱数生成器と呼ぶ。
• rand()関数は安全でない疑似乱数生成器の例。暗号には絶対に使ってはいけない！

➢ 乱択アルゴリズム𝐴(𝑥; 𝑟)を模倣するためには、
任意の入力𝑥 ∈ 0,1 ∗ について𝐴 𝑥; − ∈ 𝒞となる疑似乱数生成器𝐺を使えばよい。

Pr 𝑠 𝐴 𝑥; 𝐺 𝑧𝑧∼ 0,1=1 −Pr 𝑚 𝐴 𝑥; 𝑟 = 1 < 𝜖.

𝑟∼ 0,1

パラメータの取り方について➢ 𝐺: 0,1 𝑠 → 0,1 𝑚 ：クラス𝒞に対して安全な疑似乱数生成器•

𝐺を使うことで、𝑚ビットの乱数列を𝑠ビットに減らせる。

•

理想的には𝑠 = 𝑂(log 𝑚)ビットに減らしたい。

➢ クラス𝒞 ≔ {線形サイズの論理回路} = {𝐶: 𝑚-size circuits}∀𝐶 ∈ 𝒞,Pr 𝑠 𝐶 𝐺 𝑧

𝑧∼ 0,11= 1 − Pr 𝑚 𝐶 𝑟 = 1 < .
𝑟∼ 0,1𝑚

特に、 （𝐴の計算時間 ≪ 𝑚となるように𝑚を十分大きくとると） 𝐴 𝑥; − ∈ 𝒞であるので、
1
Pr 𝐴 𝑥; 𝐺 𝑧 = 1 − Pr 𝑚 𝐴 𝑥; 𝑟 = 1 < .
∀𝑥,𝑧∼ 0,1 𝑠𝑟∼ 0,1𝑚

∃ 疑似乱数生成器 ⟹ BPP = P (脱乱択化)➢ ∃ 疑似乱数生成器 𝐺 = 𝐺𝑚 : 0,1 𝑂 log 𝑚 → 0,1 𝑚 が 𝑚𝑂(1) 時間で計算可能だとし、線形サイズの回路に対して安全だと仮定する。
➢ 判定問題𝑓 ∈ BPPと𝑓を解く乱択多項式時間アルゴリズム𝐴 𝑥; 𝑟 を取る。

3
Pr 𝐴 𝑥; 𝑟 = 𝑓(𝑥) ≥ .
𝑟∼ 0,1 𝑚
4≈

Pr𝑧∼ 0,1 𝑂 log 𝑚

𝐴 𝑥; 𝐺𝑚 𝑧

𝑚 ≔ poly(𝑛) とする。

（安全性より） ← 𝐶𝑥 𝑟 ≔ 𝐴 𝑥; 𝑟 ⊕ 𝑓 𝑥 ⊕ 1という回路を考える。

32= 𝑓(𝑥) ≥ − 0.01 ≥ .
4
3➢ 新しいアルゴリズム𝐴 𝑥; 𝐺𝑚 𝑧 は𝑂 log 𝑚 ビットの乱数列しか使わない！
• 全ての乱数列を全探索することで、2𝑂 log 𝑚 = poly(𝑛) 時間で模倣できる。
• 従って、𝑓 ∈ P。

計算的識別不可能性 (computationally indistinguishable)➢ より一般に、 0,1 ∗ 上の二つの確率分布𝑋, 𝑌に対して、任意の小さい回路𝐶について、

Pr 𝐶 𝑋 = 1 ≈ Pr 𝐶 𝑌 = 1
𝑋

𝑌のとき、𝑋と𝑌は計算的に識別不可能という。このとき、

𝑋 ≈𝑐 𝑌と書く。（𝑐: computationally）➢ 疑似乱数生成器𝐺: 0,1 𝑠 → 0,1 𝑚 は
𝐺 𝒰𝑠 ≈𝑐 𝒰𝑚
を満たす。ただし、𝒰𝑛 は 0,1 𝑛 上の一様分布。

概要
1. 脱乱択化の理論• 理論の概要• 疑似乱数生成器の概念• 疑似乱数生成器の構成

2. メタ計算量と平均時計算量について• メタ計算問題• 平均時計算量• 最悪時・平均時計算量の同値性• 暗号との関係

PRGの構成のための３つの証明技法
1. 識別可能性 ⟺ 次のビットの予想可能性（Next-bit predictor）
𝐺: 0,1 𝑛 → 0,1 𝑛+1 ：1ビット延長できる
2. 混成分布に基づく議論（Hybrid argument）

𝐺: 0,1 𝑛𝑘 → 0,1 𝑛𝑘+𝑘 ： 𝑘ビット延長できる
3. 組合せデザイン（Combinatorial design）
𝐺: 0,1 𝑂(log 𝑚) → 0,1 𝑚 ：指数的に延長できるもっとも単純な疑似乱数生成器の構成➢ 非自明な疑似乱数生成器 𝐺: 0,1 𝑛 → 0,1 𝑛+1 を構成する。
主張 [Yao’82]
෫ 2𝜖𝑛 ; 𝛿 ならば、指数サイズの回路クラスに対して𝛿-安全かつE ⊈ io-SIZE
指数時間で計算可能な疑似乱数生成器𝐺: 0,1 𝑛 → 0,1 𝑛+1 が存在する。
➢ ℎ ∈ S෫IZE 𝑠 𝑛 ; 𝛿 : 関数ℎ: 0,1 ∗ → 0,1 は次を満たす。任意の𝑛について、
サイズ𝑠(𝑛)の回路𝐶が存在して、ℎ𝑛 ≔ ℎȁ 0,1 𝑛 を𝛿-近似する、つまり
1
Pr 𝑛 𝐶 𝑥 = ℎ𝑛 𝑥 ≥ + 𝛿 .
𝑥∼ 0,12
෫ 2𝜖𝑛 ; 𝛿 なる関数ℎ: 0,1 ∗ → 0,1 をとる。
➢ ℎ ∈ E ∖ io-SIZE

疑似乱数生成器の構成
𝐺: 0,1 𝑛 → 0,1 𝑛+1 ,𝐺 𝑧 ≔ 𝑧, ℎ𝑛 𝑧 ∈ 0,1 𝑛+1 .

構成:
主張:

証明:

𝐺に対する𝛿-統計的検定 𝐷: 0,1 𝑛+1 → {0,1} が存在するならば、𝜖𝑛（𝐷:
回路サイズ2）ℎが小さい回路で近似できる。
⟹ ℎ ∉ io-S෫
IZE 2𝜖𝑛 ; 𝛿 に矛盾。
⟹ 𝐺は安全な疑似乱数生成器。
Pr 𝑛 𝐷 𝐺 𝑧

𝑧∈ 0,1=1 −Pr 𝑛+1 𝐷 𝑤 = 1 ≥ 𝛿.

𝑤∈ 0,1⟹

Pr 𝑛 𝐷 𝐺 𝑧

𝑧∈ 0,1ℎ ∈ E: 回路で近似困難な関数=1 −Pr 𝑛+1 𝐷 𝑤 = 1 ≥ 𝛿𝑤∈ 0,1orPr𝑧∈ 0,1 𝑛

𝐷 𝐺 𝑧

=1 −

Pr

⟹

一般性を失わず、左の場合のみを考えればよい。

Pr 𝑛 𝐷′ 𝐺 𝑧𝑧∈ 0,1

𝐷 𝑤 = 1 ≤ −𝛿.

𝑤∈ 0,1 𝑛+1
𝐷′ 𝑤

=1 −

≔ ¬𝐷 𝑤 と定義

Pr 𝑛+1 𝐷′ 𝑤 = 1 ≥ 𝛿.

𝑤∈ 0,1

識別可能 ⟹ 次のビットを予測可能
主張:

𝐺に対する𝛿-統計的検定 𝐷: 0,1 𝑛+1 → {0,1} が存在するならば、ℎを2𝜖𝑛 サイズの回路で近似できる。
（𝐷: 回路サイズ2𝜖𝑛 ）Pr𝑧∈ 0,1 𝑛

𝐷 𝑧, ℎ𝑛 𝑧

=1 −

Pr

𝑤∈ 0,1 𝑛+1

𝐷は次の二つの分布を識別できる：

𝐷 𝑤 = 1 ≥ 𝛿.

(1) 𝑧, ℎ𝑛 𝑧(2) 𝑧, 𝑏（ただし、𝑧 ∼ 0,1 𝑛 ）（ただし、𝑧 ∼ 0,1 𝑛 , 𝑏 ∼ {0,1}）[Yao’82]⟹ 𝐷を用いて “next-bit predictor” 𝑃𝐷 を構成できる。

𝐺 𝑧 の最初の𝑛ビットが与えられたときに、次のビットを予測できる。
𝑧ℎ𝑛 𝑧(Cf. rand()関数の次のビットを予測できる。)

識別可能 ⟹ 次のビットを予測可能
主張:

𝐺に対する𝛿-統計的検定 𝐷: 0,1 𝑛+1 → {0,1} が存在するならば、ℎを2𝜖𝑛 サイズの回路で近似できる。
（𝐷: 回路サイズ2𝜖𝑛 ）Pr𝑧∈ 0,1 𝑛

𝐷 𝑧, ℎ𝑛 𝑧

=1 −

Pr

𝑧∈ 0,1 𝑛𝑏∈{0,1}𝐷 𝑧, 𝑏 = 1 ≥ 𝛿.

“next-bit predictor” 𝑃𝐷 の構成方法：
𝑃𝐷 𝑧; 𝑏 = ቊ𝑏𝑏⊕1

if 𝐷 𝑧, 𝑏 = 1
otherwise（ここで、𝑏 ∼ {0,1}）

アイディア: もし 𝐷 𝑧, 𝑏 = 1 ならば ℎ𝑛 𝑧 = 𝑏 である確率が高いはず。

事実:

Pr 𝑃𝐷 𝑧; 𝑏𝑧,𝑏= ℎ𝑛 𝑧1≥ +𝛿
2⟹ ℎ𝑛 が 𝛿-近似できる。

事実の証明
事実:仮定:

𝑃𝐷 𝑧; 𝑏Pr 𝑃𝐷 𝑧; 𝑏𝑧Pr 𝑛 𝐷 𝑧, ℎ𝑛 𝑧𝑧∼ 0,1= ℎ𝑛 𝑧=1 −⟹Pr 𝑛 𝐷 𝑧, 𝑏 = 1 ≥ 𝛿.

𝑧∼ 0,1𝑏∼{0,1}1= 1 + Pr 𝐷 𝑧, ¬ℎ𝑛 𝑧
2 𝑧

=1 .

(𝑏 = ℎ𝑛 𝑧 or 𝑏 = ¬ℎ𝑛 𝑧 )1
Pr 𝐷 𝑧, ℎ𝑛 𝑧
2 𝑧∼ 0,1 𝑛
Pr 𝑃𝐷 𝑧; 𝑏 = ℎ𝑛 𝑧𝑧,𝑏if 𝐷 𝑧, 𝑏 = 1
otherwise

1
≥ +𝛿
2

1
Pr 𝐷 𝑧, 𝑏 = 1 = Pr 𝐷 𝑧, ℎ𝑛 𝑧𝑧∼ 0,1 𝑛
2 𝑧𝑏∼{0,1}

𝑏
=ቊ
𝑏⊕1

1
= 1 − Pr 𝐷 𝑧, ¬ℎ𝑛 𝑧
2 𝑧
1= Pr 𝐷 𝑧, ℎ𝑛 𝑧
21
= Pr 𝐷 𝑧, ℎ𝑛 𝑧
2

= 1 ≥ 𝛿.
(𝑏 = ℎ𝑛 𝑧 or 𝑏 = ¬ℎ𝑛 𝑧 )1= 1 + Pr 𝐷 𝑧, ¬ℎ𝑛 𝑧 = 02
1 1
1= 1 + − Pr 𝐷 𝑧, ¬ℎ𝑛 𝑧 = 1 ≥ + 𝛿.
2 22

単純な疑似乱数生成器の構成のまとめ
主張 [Yao’82]
෫ 2𝜖𝑛 ; 𝛿 ならば、指数サイズの回路クラスに対して𝛿-安全かつE ⊈ io-SIZE
指数時間で計算可能な疑似乱数生成器𝐺: 0,1 𝑛 → 0,1 𝑛+1 が存在する。
➢ 構成:
෫ 2𝜖𝑛 ; 𝛿 となる計算困難な関数ℎ: 0,1 ∗ → 0,1 をとる。
• ℎ ∈ E ∖ io-SIZE•𝑧 ∈ 0,1 𝑛 に対して 𝐺 𝑧 ≔ 𝑧, ℎ 𝑧∈ 0,1 𝑛+1 と定める。

➢ 証明のアイディア: 背理法
𝐷 が 𝐺(−)に対する統計的検定 ⟹ 𝑃𝐷 : “next-bit predictor”が構成できる。

PRGの構成のための３つの証明技法
1. 識別可能性 ⟺ 次のビットの予想可能性（Next-bit predictor）
𝐺: 0,1 𝑛 → 0,1 𝑛+1 ：1ビット延長できる
2. 混成分布に基づく議論（Hybrid argument）

𝐺: 0,1 𝑛𝑘 → 0,1 𝑛𝑘+𝑘 ： 𝑘ビット延長できる
3. 組合せデザイン（Combinatorial design）
𝐺: 0,1 𝑂(log 𝑚) → 0,1 𝑚 ：指数的に延長できる𝑘ビットの拡張• 計算困難な関数ℎ: 0,1 𝑛 → 0,1 をとる。
• 𝐺 ℎ : 0,1 𝑛 → 0,1 𝑛+1 ：1ビット拡張する疑似乱数生成器
𝐺 ℎ 𝑧 ≔ 𝑧, ℎ 𝑧 .

ℎ の困難性⟹ 𝐺 ℎ の安全性

• これを𝑘ビットに拡張したい。
DP𝑘ℎ : 0,1 𝑛𝑘 → 0,1 𝑛𝑘+𝑘𝑘ℎℎDP𝑘 ≔ 𝐺
DP𝑘ℎ 𝑧1 , … , 𝑧𝑘

≔ 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑘

𝑘ビットの拡張: 𝑘-wise Direct Product Genertor主張෫ 2𝜖𝑛 ; 𝛿/𝑘 ならば、ある疑似乱数生成器
E ⊈ io-SIZE
DP𝑘 : 0,1 𝑘𝑛 → 0,1 𝑘𝑛+𝑘が存在して、2𝜖𝑛 サイズの回路に対して𝛿-安全で、2𝑂(𝑛) 時間で計算可能。
➢ 構成: 𝑘-wise Direct Product Generator （𝑘直積生成器）•

෫ 2𝜖𝑛 ; 𝛿/𝑘 なるものをとる。
関数ℎ: 0,1 ∗ → 0,1 であって ℎ ∈ E ∖ io-SIZE•

DP𝑘ℎ : 0,1 𝑛 𝑘 → 0,1 𝑛𝑘+𝑘 を次のように定める。
DP𝑘ℎ 𝑧1 , … , 𝑧𝑘 ≔ 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑘 .

アイディア: Hybrid Argument
DP𝑘ℎ : 0,1 𝑛 𝑘 → 0,1 𝑛𝑘+𝑘ℎDP𝑘 𝑧1 , … , 𝑧𝑘 ≔ 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑘 .
➢ DP𝑘ℎ − に対する統計的テスト𝐷が存在したとする。すなわち：

Pr

𝑧1 ,…,𝑧𝑘➢

𝐷 DP𝑘ℎ 𝑧1 , … , 𝑧𝑘

𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑘

= 1 − 𝑧 Pr
𝐷 𝑧1 , … , 𝑧𝑘 , 𝑏1 , … , 𝑏𝑘 = 1 ≥ 𝛿,…,𝑧1𝑘𝑏1 ,…,𝑏𝑘と 𝑧1 , … , 𝑧𝑘 , 𝑏1 , … , 𝑏𝑘 を直接比べるのは難しい。

➢ Hybrid argument ：二つの分布を補間する分布𝐻0 , 𝐻1 , … , 𝐻𝑘 を考える。

混合分布に基づく議論（Hybrid Argument）
Pr

𝑧1 ,…,𝑧𝑘

𝐷 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑘
≡ 𝐻𝑘

= 1 − 𝑧 Pr
𝐷 𝑧1 , … , 𝑧𝑘 , 𝑏1 , … , 𝑏𝑘 = 1 ≥ 𝛿
1 ,…,𝑧𝑘
𝑏1 ,…,𝑏𝑘≡ 𝐻0➢ 𝑖番目の混合分布 𝐻𝑖 ≡ 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑖 , 𝑏𝑖+1 … , 𝑏𝑘
（ここで、𝑖 ∈ 0, … , 𝑘 , 𝑧1 , … , 𝑧𝑘 ∼ 0,1 𝑛 , 𝑏1 , … , 𝑏𝑘 ∼ {0,1}）𝑘𝛿 ≤ Pr 𝐷 𝐻𝑘 = 1 − Pr 𝐷 𝐻0 = 1 = ෍(Pr 𝐷 𝐻𝑖 = 1 − Pr 𝐷 𝐻𝑖−1 = 1 )
𝑖=1

⟹

𝛿
（ある𝑖 ∈ {1, … , 𝑘}について）≤ Pr 𝐷 𝐻𝑖 = 1 − Pr 𝐷 𝐻𝑖−1 = 1𝑘= Pr 𝐷 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑖 , 𝑏𝑖+1 , … , 𝑏𝑘 = 1 − Pr 𝐷 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , 𝑏𝑖 , 𝑏𝑖+1 … , 𝑏𝑘 = 1= 𝔼 𝐷 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑖 , 𝑏𝑖+1 , … , 𝑏𝑘 − 𝐷 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , 𝑏𝑖 , 𝑏𝑖+1 … , 𝑏𝑘⟹.

期待値を最大化するような𝑧𝑗 , 𝑏𝑗 を全ての𝑗 ∈ 1, … , 𝑘 ∖ {𝑖}について固定し、𝐷′ 𝑧𝑖 , 𝑏𝑖 ≔ 𝐷 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , 𝑏𝑘 と定めると、
Yao’s next-bit predictor

Pr 𝐷′ 𝑧𝑖 , ℎ 𝑧𝑖
𝑧𝑖

= 1 − Pr 𝐷′ 𝑧𝑖 , 𝑏𝑖 = 1 ≥ 𝛿/𝑘𝑧𝑖 ,𝑏𝑖⟹ℎ ∈ S෫
IZE 2𝜖𝑛 ; 𝛿/𝑘 .

PRGの構成のための３つの証明技法
1. 識別可能性 ⟺ 次のビットの予想可能性（Next-bit predictor）
𝐺: 0,1 𝑛 → 0,1 𝑛+1 ：1ビット延長できる
2. 混成分布に基づく議論（Hybrid argument）

𝐺: 0,1 𝑛𝑘 → 0,1 𝑛𝑘+𝑘 ： 𝑘ビット延長できる
3. 組合せデザイン（Combinatorial design）
𝐺: 0,1 𝑂(log 𝑚) → 0,1 𝑚 ：指数的に延長できる

指数的に乱数の種を延長する➢ 𝑘直積生成器では、独立な入力で計算困難関数ℎを計算する。
DP𝑘ℎ :

𝑧1 , … , 𝑧𝑘 ↦ 𝑧1 , … , 𝑧𝑘 , ℎ 𝑧1 , … , ℎ 𝑧𝑘
ℎ は計算困難 ⟹ DP𝑘ℎ は安全。

➢ ℎを相関のある指数個の入力で計算する。
NWℎ : 𝑧 ↦𝑧𝑆1 , … , 𝑧𝑆𝑚 ↦ ℎ 𝑧𝑆1 , … , ℎ 𝑧𝑆𝑚

指数的に乱数の種を伸ばす
定理 [Nisan & Wigderson ’94]
෫ 2𝜖𝑛 ; 2−𝜖𝑛 ならば、あるある定数𝜖 > 0についてE ⊈ io-SIZE
疑似乱数生成器 NW = NW𝑁 : 0,1 𝑂 log 𝑁 → 0,1 𝑁 𝑁∈ℕ であって、• サイズ𝑁回路に対して安全で、かつ• 𝑁 𝑂(1) 時間で計算可能なものが存在する。特に、P = BPP。

•ℎ: 0,1 𝑛 → 0,1 : 計算困難な関数として、
NW𝑁 : 0,1 𝑂(log 𝑁) → 0,1 𝑁
NWℎ 𝑧 ≔ ℎ 𝑧𝑆1 , … , ℎ 𝑧𝑆𝑁

詳細は演習問題

ただし、𝑛 = 𝑂 log 𝑁 。

Eに対する最悪時・平均時計算量の同値性[Nisan-Wigderson ’94]

෫ 2𝜖𝑛 ; 2−𝜖𝑛 ⟹ P = BPP
E ⊈ ‫>𝜖ځ‬0 io-SIZE⟺[Impagliazzo-Wigderson ’97]

局所リスト復号可能誤り訂正符号E ⊈ ‫>𝜖ځ‬0 io-SIZE 2𝜖𝑛 ⟹ P = BPP

局所リスト復号可能誤り訂正符号 Enc: 𝑓 ↦ Enc(𝑓) の性質
1. 𝑓 ∈ E ⟹ Enc 𝑓 ∈ E.

2.

[Sudan-Trevisan-Vadhan ’01]

′𝑛
𝜖𝑛
−𝜖𝑛
𝜖
෫
Enc 𝑓 ∈ io-SIZE 2 ; 2⟹ 𝑓 ∈ io-SIZE 2.

Hardness versus Randomness Trade-off
EXP ⊈ ioSIZE 𝑛𝑂 1

⟹ BPP ⊆ SUBEXP ≔ ሩ DTIME 2𝑛(∃ PRG 𝐺: 0,1𝑛𝜖

EXP ⊈ ሩ ioSIZE 2
𝜖>0

𝑚𝜖

.

𝜖>0

→

𝜖
𝑚
𝑚
0,1 , computable in time 2 )⟹ BPP ⊆ QuasiP ≔ DTIME 2(∃ PRG 𝐺: 0,1

𝜖log 𝑚 𝑂(1) →log 𝑛 𝑂 1

.

𝑂 1
𝑚
log
𝑚
0,1 , computable in time 2)

E ⊈ ሩ ioSIZE 2𝜖𝑛 ⟹ BPP ⊆ P.
𝜖>0(∃ PRG 𝐺: 0,1 𝑂 log 𝑚 → 0,1 𝑚 , computable in time 𝑚𝑂(1) )疑似乱数生成器の理論の応用➢ Randomness extractor の構成 [Trevisan ’01]
➢ AC 0 [⊕]（PARITY付き定数段回路 ）を準指数時間で学習。
[Carmosino, Impagliazzo, Kabanets, Kolokolova (CCC’16)]➢ 非ブラックボックスな最悪時・平均時帰着 [H. FOCS’18]
これらの結果は、疑似乱数生成器の理論をメタ的にみることによって得られる。

脱乱択化の理論のまとめ➢ どのように乱択アルゴリズム𝐴(𝑥; 𝑟)を模倣すべきか• 𝐴(𝑥; 𝑟)に対して安全な疑似乱数生成器を使うべき。
rand()関数で振る舞いが変わりそうなときは使ってはダメ• 回路下界（計算困難性） ⟹ 安全な疑似乱数生成器が構成可能。

参考文献：Salil Vadhan, “Pseudorandomness”, 2012より最近の発展については：Lijie Chen, Roei Tell ”New ways of studying the BPP = P conjecture”, 2023

概要
1. 脱乱択化の理論• 理論の概要• 疑似乱数生成器の概念• 疑似乱数生成器の構成

2. メタ計算量と平均時計算量について• メタ計算問題• 平均時計算量• 最悪時・平均時計算量の同値性• 暗号との関係

メタ計算量と平均時計算量➢ メタ計算量：「計算量を問う問題の計算量」• メタ計算問題の代表例：MCSP（回路最小化問題）、MINKT• これらのメタ計算問題に対して最悪時・平均時帰着が存在 [H. FOCS’18]。
➢ 平均時計算量• 中心的未解決問題：NPの最悪時・平均時計算量は同値か？
Cf. EXPやPSPACEの最悪時・平均時計算量は同値（∵ 局所リスト復号可能誤り訂正符号）。

• メタ計算問題がNP完全であれば、肯定的に解決できる！

メタ計算量（Meta-complexity）➢ メタ計算量：計算量を問う計算問題の計算量のこと。
• 近年の理論計算機科学におけるホットトピックのひとつ➢ 計算量（complexity, 複雑さ）

• 計算に必要な資源のこと
例: 計算時間、メモリ、回路サイズ、記述量➢ 𝐏 ≠ 𝐍𝐏予想の同値な言いかえ：• 三彩色問題を解くための計算時間は超多項式的か？
• 特に、三彩色問題 ∉ SIZE(𝑛𝑂(1) ) を示すことができれば、P ≠ NP。

回路計算量の歴史➢ 関数𝑓を計算する最小の回路サイズ（回路計算量; Circuit Complexity）をCC(𝑓)と書く。
➢ 一様ランダムな関数𝑓: 0,1 𝑛 → {0,1}について、CC 𝑓 ≈ 2𝑛 /𝑛 [Shannon 1949]• CC 三彩色問題 ≥ 𝑛𝜔 1 ⟹ P ≠ NP
（ある関数𝑓 ∈ P について、𝐵2 = 𝑔: 0,1 2 → 0,1 基底に対して）
CC 𝑓 ≥ 2𝑛 − 𝑂(1) [Kloss & Malyshev 1965]

CC 𝑓 ≥ 2.5𝑛 − 𝑂(1) [Stockmeyer 1977]
CC 𝑓 ≥ 3𝑛 − 𝑜(𝑛) [Blum 1984]

CC𝑈2 𝑓 ≥ 5𝑛 − 𝑜(𝑛) [Iwama & Morizumi 2002]… 約３０年の時が流れる
CC 𝑓 ≥ 3.011𝑛 − 𝑜(𝑛) [Find, Golovnev, Hirsch, and Kulikov (FOCS 2016)]
CC 𝑓 ≥ 3.1𝑛 − 𝑜(𝑛) [Li & Yang (STOC 2022)]

回路計算量をメタ的にみる➢ ここまでは具体的な関数𝑓: 0,1 𝑛 → {0,1}の回路計算量を考えた。
(explicit; 𝑓 ∈ P や 𝑓 ∈ NP などを意味する)➢ しかし、回路計算量の計算は（人間には）難しい！
• アルゴリズムにとっても難しいはず。
➢ 回路計算量を計算するための計算量は？ ⟹ 回路最小化問題➢ 回路計算量の計算が多項式時間アルゴリズムに対しても難しいことを示せれば、P ≠ NP。
•

Andrey Kolmogorov: 同様のアプローチをコルモゴロフ記述量に基づいて提唱 （1960年代）

回路計算量を計算する問題

MCSP (Minimum Circuit Size Problem; 回路最小化問題)
入力

出力• ブール値関数 𝑓: 0,1 𝑛 → 0, 1 の𝑛
真理値表 （𝑓 ∈ 0,1 2 と同一視）• 閾値𝑠 ∈ ℕ

CC 𝑓 ≤ 𝑠 ?

ゲート数𝑠以下の論理回路で関数𝑓を計算するものが 1存在するかどうか。

1
0

1

例

• 𝑓 = ⊕2 （2入力XOR）
• 𝑠=5
𝒙𝟏

𝒙𝟐

𝒙𝟏 ⊕ 𝒙𝟐

0

0

0

0

1

1

1

0

1

1

1

0

0

YES
（∵ 右図のような論理回路が存在する）

0

1

簡単な事実: MCSP ∈ NP = NTIME 𝑁 𝑂 1(𝑁 ≔ 2𝑛 , 入力長)
MCSP ∈ DTIME 2𝑂 𝑁
重要な未解決問題: MCSPはNP完全か？
NP完全性の概念がCookとLevinによって導入された1970年代初頭から未解決。

回路最小化問題は「圧縮」の問題➢ 回路最小化問題は、
𝑛2「入力文字列𝑓 ∈ 0,1 を小さい回路𝐶で𝑓を圧縮表現できるか」という問題だとみなせる。
• サイズ𝑠の回路は𝑂 𝑠 log 𝑠 + 𝑛≪ 2𝑛 ビットで表現できるから。

➢ コルモゴロフ記述量：最適な圧縮の方法• より効率的に圧縮できるので、メタ計算量の研究ではより扱いやすい。
• K 𝑥 = (𝑥を出力する最小のプログラムの長さ)

コルモゴロフ記述量(decompressor)

解凍機の例：unzip、Pythonのインタプリタ➢ 解凍機𝑀に関する文字列𝑥 ∈ 0,1 ∗ のコルモゴロフ記述量
K 𝑀 𝑥 = min 𝑑 ∶ 𝑀 𝑑 = 𝑥 .
➢ 普遍チューリング機械𝑈をとると、コルモゴロフ記述量はほぼ最小になる。

• 任意のチューリング機械𝑀に対して、ある𝑑𝑀 ∈ 0,1 ∗ が存在して、𝑈 𝑑𝑀 , 𝑥 = 𝑀 𝑥 .
• 従って、任意の機械𝑀について、ある定数𝑐𝑀 が存在して、K 𝑈 𝑥 ≤ K 𝑀 𝑥 + 𝑐𝑀 .
➢ 以降、𝑈を一つ固定して、K 𝑥 ≔ K 𝑈 (𝑥)と略記する。

時間制限付きコルモゴロフ記述量➢ 文字列𝑥の𝑡時間制限付きコルモゴロフ記述量とは
K 𝑡 𝑥 ≔ min 𝑑 ∶ 入力𝑑で𝑈が𝑥を𝑡時間以内で出力する .

例• K 𝑡 00 … 0 = log 𝑛 + 𝑂 1 （ただし、𝑡 ≫ 𝑛.）← print “0” × 𝑛

𝑛回繰り返し（0𝑛 と書く）

（ただし、𝑡 ≫ 𝑛、𝑥 ∈ 0,1 𝑛 ）• K 𝑡 𝑥 ≤ 𝑛 + 𝑂(1)•34

Pr 𝑛 K 𝑥 ≥ 𝑛 − 2 ≥ .

𝑥∼ 0,1← print “𝑥”← 数え上げの議論（演習問題）

コルモゴロフ記述量を計算する問題

MINKT （時間制限付きコルモゴロフ記述量問題）
入力

出力• 文字列𝑥 ∈ 0,1 ∗• サイズパラメタ𝑠 ∈ 0,1 ∗• 時間パラメタ1𝑡（一進法で書く）

K𝑡 𝑥 ≤ 𝑠 ?

文字列𝑥を時間制限𝑡以内で出力する𝑠ビット以下のプログラムが存在するか。

➢ 言語として定義すると、MINKT ≔𝑥, 1𝑡 , 1𝑠

K𝑡 𝑥 ≤ 𝑠

簡単な事実: MINKT ∈ NP
MINKT ∈ DTIME 2𝑂 𝑁

(𝑁 = Θ 𝑥 + 𝑡 : 入力長)

重要な未解決問題: MINKTはNP完全か？

概要
1. 脱乱択化の理論• 理論の概要• 疑似乱数生成器の概念• 疑似乱数生成器の構成

2. メタ計算量と平均時計算量について• メタ計算問題• 平均時計算量• 最悪時・平均時計算量の同値性• 暗号との関係

平均時計算量と最悪時計算量➢ 二つの計算量の概念

悲観的すぎることが多い• 最悪時計算量：計算時間が最も大きくなる入力での計算時間• 平均時計算量：入力をランダムにとったときの平均計算時間➢ 例：NP完全問題

P
SIZE(𝑠)෫ 𝑠
AvgP SIZE

より現実に
即している

• 実応用上は、NP完全問題であってもSATソルバーで高速に解けることが多い。

• 理論的にも、いくつかのNP完全問題は自然な入力分布上で平均時多項式時間で解ける。
✓ ハミルトンパス問題はErdős–Rényiランダムグラフ上で期待線形時間で解ける。
[Gurevich & Shelah (1987)]➢ 脱乱択化や暗号理論においても平均時計算量が重要となる。

DistNP: 平均時計算量版のNP➢ 𝐿, 𝒟 : 分布問題 (distributional problem)
判定問題𝐿と入力分布𝒟 = 𝒟𝑛 𝑛∈ℕ の組のこと。
➢ どのような入力分布を考えるべきか？
→ 実用上現れる入力は効率的にサンプル可能な分布から生成されているはず
𝒟 = 𝒟𝑛 𝑛∈ℕ が多項式時間サンプル可能であるとは、

ある乱択多項式時間アルゴリズム𝐴が存在して、Pr 𝐴 1𝑛 = 𝑥 = Pr 𝑋 = 𝑥
𝐴となることを言う。
➢ DistNP ≔𝑋∼𝒟𝑛

𝐿, 𝒟 𝐿 ∈ NP, 𝒟: 多項式時間サンプル可能（NPの分布問題版）

効率的サンプル可能な分布だけを考える！

AvgP: 平均時多項式時間計算可能な分布問題
AvgP ≔

𝐿, 𝒟

平均時多項式時間計算可能な分布問題 𝐿, 𝒟

[Levin’86]

𝐴が(𝐿, 𝒟)に対する平均時多項式時間アルゴリズムであるとは、任意の𝑛 ∈ ℕについて、以下の二つの条件を満たす。
1. 任意の𝑥 ∈ supp 𝒟𝑛 について、 𝐴 𝑥, 1 = 𝐿 𝑥 .
2. ある定数𝜖 > 0に対して、𝔼𝑥∼𝒟𝑛 𝑡𝐴 𝑥, 1𝑛 𝜖 ≤ 𝑛𝑂 1 .
ただし、𝑡𝐴 (𝑥, 1𝑛 )は𝐴の入力 𝑥, 1𝑛 における計算時間。
𝑛定数𝜖:
定義をロバストにするために必要。

誤りなしヒューリスティクスを用いて、同値な定義が与えられる。（演習問題）※ 本講演の全ての分布では、𝑥 ∈ supp(𝒟𝑛 )から1𝑛 が計算可能なので、以降では1𝑛 は省略する。
例：𝒰 = 𝒰𝑛 𝑛∈ℕ ： 0,1 𝑛 上の一様分布。

NPの最悪時計算量 と 平均時計算量
中心的未解決問題 Heuristicaを除外できるかP ≠ NP?
⟹DistNP ⊈ AvgP

（NPが最悪時計算量の意味で計算困難であれば、ある多項式時間サンプル可能な分布上においてNPが平均時計算量の意味で計算困難か？）➢ より安全な暗号を構築するための重要な一歩

本質的には一様分布だけを考えても一般性を失わない[Impagliazzo-Levin’90]➢ なぜ解決するのが難しいのか？ ← 理論的障壁「ブラックボックス帰着の限界」「困難性増幅の不可能性」「相対化のバリア」

概要
1. 脱乱択化の理論• 理論の概要• 疑似乱数生成器の概念• 疑似乱数生成器の構成

2. メタ計算量と平均時計算量について• メタ計算問題• 平均時計算量• 最悪時・平均時計算量の同値性• 暗号との関係

MCSPの最悪時・平均時計算量の同値性➢ ブラックボックス帰着の限界 [Bogdanov & Trevisan ’06]
• 問題𝐿がDistNPに（非適応的）乱択多項式時間で帰着できるならば、𝐿 ∈ coNP/poly。
•

帰着を構成するような標準的な手法では、NP完全問題をDistNPに帰着できない。
（NP ⊆ coNP/polyでない限り）

定理 [H. (FOCS 2018)]

𝒰: 一様分布として、以下は同値。
1. ある定数𝜖 > 0について、 MCSP[2𝜖𝑛 ], 𝒰 ∈ AvgBPP。
MCSP 2𝜖𝑛 : サイズパラメタが2𝜖𝑛 に固定された回路最小化問題
2. ある定数𝜖 > 0について、Gap𝜖 MCSP ∈ BPP。
Gap𝜖 MCSP: 回路計算量の2 1−𝜖 𝑛 倍近似を計算する問題➢ ブラックボックス帰着の限界の限界を突破する初めての結果。
•[Rudich’97]の予想：Gap𝜖 MCSP ∉ coNP/poly約束付き問題Gap𝜖 MCSPの定義➢ 近似問題は約束付き問題Π = ΠYES , ΠNO によって定式化される。

➢ アルゴリズム𝐴がΠ = ΠYES , ΠNO を解くとは、全ての𝑥で以下が成立すること。
1 𝑥 ∈ ΠYES ⟹ 𝐴 𝑥 = 1,
2 𝑥 ∈ ΠNO ⟹ 𝐴 𝑥 = 0.
➢ Gap𝜖 MCSP ≔ Gap𝜖 MCSPYES , Gap𝜖 MCSPNO
Gap𝜖 MCSPYES = 𝑓 CC 𝑓 ≤ 2𝜖𝑛Gap𝜖 MCSPNO = 𝑓 CC 𝑓 ≥ 2 1−𝜖 𝑛➢ 事実： ある定数𝜖 > 0について、⟺ ある定数𝜖 > 0と多項式時間アルゴリズム𝐴が存在し、1−𝜖 𝑛Gap𝜖 MCSP ∈ P

CC 𝑓 ≤ 𝐴 𝑓 ≤ CC 𝑓 ⋅ 2を満たす。

証明のアイディア➢ “Hardness versus Randomness”の枠組みをメタ的に適用する。
➢ ほとんど全ての疑似乱数生成器の構成は「ブラックボックス」である。
[Impagliazzo-Wigderson’97]

任意の計算困難な関数
𝑓 ∉ SIZE 20.01𝑛↦

疑似乱数生成器IW𝑓 : 0,1 𝑂 log 𝑁 → 0,1 𝑁• このような写像IW ⋅ を疑似乱数生成器の構成と呼ぶ。
➢ 実は、疑似乱数生成器の構成が平均時・最悪時帰着になっている。

“Hardness versus Randomness” をメタ的に適用➢ 伝統的な “Hardness versus Randomness” の枠組みでは仮定：固定された 計算困難関数
0.01𝑛𝑓 ∈ 𝐄 ∖ io−SIZE 2↦

疑似乱数生成器
𝐺 𝑓 : 0,1 𝑂 log 𝑁 → 0,1 𝑁➢ この枠組みをメタ計算量的に解釈する。
• 𝑓を𝐌𝐂𝐒𝐏の入力だとする。

• 𝑓 ↦ 𝐺 𝑓 𝑧 をMCSPに対する乱択帰着だとみなす。
𝐺 𝑓 𝑧 ∈ 0,1 𝑁 を関数 0,1 log 𝑁 → 0,1 の真理値表と同一視する。

NOインスタンス 𝑓 ∉ SIZE 20.9𝑛

↦

最悪の入力
YESインスタンス 𝑓 ∈ SIZE 20.1𝑛

𝐺 𝑓 𝑧 ≈𝑐 𝒰 ∉ SIZE 𝑁 0.99 (w.h.p)
平均的な（疑似的に一様な）入力↦

𝐺 𝑓 𝑧 ∈ SIZE 𝑁 0.99

平均時多項式時間アルゴリズムを𝐴として、最悪時多項式時間アルゴリズム𝐵をつくる。

主張： MCSP[2𝑛/2 ], 𝒰 ∈ AvgP ⟹ Gap𝛾 MCSP ∈ BPP
補題 [Yao’82, Nisan-Wigderson’94, Carmosino-Impagliazzo-Kabanets-Kolokolova’16]
任意の定数𝛾 > 0と𝑚 ∈ ℕに対し、以下のような疑似乱数生成器の構成𝐺 (⋅) が存在する。
𝑚

1. 𝑓: 0,1 𝑛 → {0,1} を 𝐺 𝑓 : 0,1 𝑑 → 0,1 2 に写す（ある𝑑 ∈ ℕに対して） 。
2. CC 𝑓 ≥ 2𝑂(𝑚+𝛾𝑛) + 2 1−𝛾 𝑛−1 ならば、 𝐺 𝑓 は2𝑂(𝑚) サイズ回路に対して安全な疑似乱数生成器。

3. 任意の𝑧に対して、CC 𝐺 𝑓 𝑧
構成：𝐺 𝑓 𝑧 ≔ NW𝑓⊕𝑘≤ CC 𝑓 ⋅ 2𝛾𝑛 。

（𝐺 𝑓 𝑧 : 0,1 𝑚 → {0,1}と同一視する。）

ただし、𝑓 ⊕𝑘 𝑥 = 𝑓 𝑥1 ⊕ ⋯ ⊕ 𝑓 𝑥𝑘 , 𝑘 = 2Θ 𝛾𝑛 .

𝑧

➢ 乱択アルゴリズム𝐵 𝑓 ：𝑧 ∼ 0,1 𝑚 を一様ランダムにとる。𝑠 ≤ 2𝛾𝑛 としてよい。
𝐵 𝑓 ≔ 1 ⟺ 𝐴 𝐺𝑓 𝑧が多項式時間で停止しない、または1と出力する。

➢ CC 𝑓 ≤ 2𝛾𝑛 のとき、CC 𝐺 𝑓 𝑧≤ 2𝛾𝑛 ⋅ 2𝛾𝑛 ≤ 2𝑚/2 。ただし、𝑚 ≔ 4𝛾𝑛。特に、Pr 𝐵 𝑓 = 1 = 1。

➢ CC 𝑓 ≥ 2 1−𝛾 𝑛 のとき、Pr 𝐵 𝑓 = 0 ≈ 1。（次ページ）
𝐵

𝐵

主張：CC 𝑓 ≥ 2 1−𝛾 𝑛 のとき、 Pr 𝐵 𝑓 = 0 ≈ 1。
𝐵

∵ 2𝑂(𝛾𝑛) + 2 1−𝛾 𝑛−1 ≤ 2 1−𝛾 𝑛 （十分小さい𝛾 > 0をとる）

CC 𝑓 ≥ 2 1−𝛾 𝑛⟹CC 𝑓 ≥ 2𝑂 𝛾𝑛 + 2 1−𝛾 𝑛−1 ⟹𝐺 𝑓 𝒰𝑑 ≈𝑐 𝒰2𝑚∵ 性質2∵ “≈𝑐 ”より

Pr 𝐵 𝑓 = 1 = Pr 𝐴′ 𝐺 𝑓 𝑧
𝐵

𝑧

𝐴′ 𝑥

= 1 ≤ Pr 𝐴′ 𝒰 = 1 + 𝑜(1)𝒰定義

≔ 1 ⟺ 𝐴 𝑥 = 1 または𝐴(𝑥)が多項式時間𝑝で停止しない。

Pr 𝐴′ 𝒰 = 1 ≤ Pr 𝑡𝐴 𝒰 ≥ 𝑝 + Pr 𝐴 𝒰 = 1 .
𝒰• Pr 𝑡𝐴 𝒰 ≥ 𝑝 ≤ Pr 𝑡𝐴

𝒰 𝜖 ≥ 𝑝𝜖

𝔼 𝑡𝐴 𝒰 𝜖≤𝑝𝜖∵ 𝐴は平均時多項式時間
2𝑂 𝑚
≤ 𝜖
𝑝

∵ Markovの不等式• Pr 𝐴 𝒰 = 1 ≤∵ 十分大きい𝑝 = 2𝑂 𝑚 をとる。

Pr 𝑚 CC 𝑓 ≤ 2𝑚/2 ≤ 𝑜 1 .

𝑓∼ 0,1 2∵ 𝐴は誤りなし≤𝑜 1 .

∵ 数え上げの議論（演習問題）

MINKTの最悪時・平均時帰着➢ MINKTの場合には、近似精度が大幅に改善できる。
定理 [H. (FOCS 2018, CCC 2020)]
DistNP ⊆ AvgPのもとで、GapMINKT ∈ P。ただし、GapMINKTYES =𝑥, 1𝑡 , 1𝑠

K𝑡 𝑥 ≤ 𝑠 .

GapMINKTNO =𝑥, 1𝑡 , 1𝑠

K poly 𝑡+ȁ𝑥ȁ 𝑥 > 𝑠 + 𝑂 log 𝑡 + 𝑥➢ ここでは𝑂(log 𝑛)倍近似問題をDistNPに帰着できることを示す。
′
GapMINKTNO=

𝑥, 1𝑡 , 1𝑠

K poly 𝑡+ȁ𝑥ȁ 𝑥 > 𝑠 ⋅ 𝑂 log ȁ𝑥ȁ .

➢ 主張：DistNP ⊆ AvgP ⟹ GapMINKT ′ ∈ BPP.

.

疑似乱数生成器の構成：𝑘直積生成器
補題 (リスト復号 [Sudan’97])
poly𝑛
時間計算可能リスト復号可能誤り訂正符号Enc:𝜖𝑛2ℓ𝑛 poly 𝜖

復号アルゴリズムDec: 0,1
1
2

→

ℓ

0,1 𝑛 → 0,1 2 とが存在して、以下を満たす。

0,1ℓ

Prℓ Enc 𝑥 𝑖 = 𝑦𝑖 ≥ + 𝜖なる𝑦 ∈ 0,1 2 が与えられたとき、Dec(𝑦)は𝑖∼ 2

リスト𝐿 ⊆ 0,1 𝑛 であって𝑥 ∈ 𝐿なるものを出力できる。ただし、𝑦𝑖 は𝑦の𝑖番目のビット。

補題 (𝑘直積生成器 [H. STOC’20])

𝑘
ℓ
0,1
→

DP𝑘 :
0,1 ℓ𝑘+𝑘 を、DP𝑘 𝑥; 𝑧1 , … , 𝑧𝑘 = 𝑧1 , … , 𝑧𝑘 , Enc 𝑥 𝑧1 , … , Enc 𝑥 𝑧𝑘 と定める。（特に、ℓ = 𝑂 log 𝑛 ）0,1 𝑛 ×K poly 𝑛,𝑡 𝑥 ≥ 𝑘 ⋅ 𝑂(log 𝑛) ならば、任意の𝑡時間アルゴリズム𝑇に対して、
Pr 𝑇 DP𝑘 𝑥; 𝑧 = 1 ≈ Pr 𝑇 𝒰 = 1 .
𝑧

𝒰主張：DistNP ⊆ AvgP ⟹ GapMINKT ∈ BPP
′

➢ 𝐿≔

𝑥, 1𝑡

K 𝑡 𝑥 ≤ 𝑥 − 2 とおく。（MINKTの閾値を𝑠 ≔ 𝑛 − 2に固定した問題）➢ 分布𝒟 = 𝒟⟨𝑛,𝑡⟩𝑛,𝑡∈ℕ⋅,⋅ : ℕ × ℕ → ℕ, 効率的全単射

を、𝒟 𝑛,𝑡 ≡ (𝒰𝑛 , 1𝑡 )として定める。

➢ 𝐿, 𝒟 ∈ DistNP ⊆ AvgPより、平均時多項式時間アルゴリズム𝐴を得る。
➢ 乱択多項式時間アルゴリズム𝐵を次のように定める。
𝐵 𝑥, 1𝑡 , 1𝑠 ; 𝑧 ≔ 1 ⟺ 𝐴 DP𝑘 𝑥; 𝑧 , 1𝑡➢′

= 1 または 多項式時間𝑝で停止しない。
ただし、𝑘 = 𝑠 + Θ log 𝑛 , 𝑡 ′ = 𝑡 + poly 𝑛 。

𝐵がGapMINKT ′ を解くことを示す。

➢ (𝑥, 1𝑡 , 1𝑠 ) ∈ GapMINKTYES のとき、つまりK 𝑡 𝑥 ≤ 𝑠のとき、 十分大きい𝑘 = 𝑠 + 𝑂(log 𝑛)をとる。
′• K 𝑡 DP𝑘 𝑥; 𝑧

≤ K 𝑡 𝑥 + 𝑧 + 𝑂 log 𝑛 ≤ 𝑠 + 𝑘ℓ + 𝑂 log 𝑛 ≤ 𝑘ℓ + 𝑘 − 2.

⟹ DP𝑘 𝑥; 𝑧 , 1𝑡 ∈ 𝐿. 従って、𝐵は受理する。
′➢ (𝑥, 1𝑡 , 1𝑠 ) ∈ GapMINKTNOのとき、つまりK poly(𝑛,𝑡) 𝑥 > 𝑠 ⋅ 𝑂 log 𝑛 = 𝑘 ⋅ 𝑂 log 𝑛 のとき、′

Pr 𝐴 DP𝑘 𝑥; 𝑧 , 1∵ DP𝑘 𝑥; 𝑧 ≈𝑐 𝒰𝑧

≲ Pr 𝐴 𝒰, 1𝑡′

𝑡′= 1 or 𝑡𝐴 DPk x; z , 1= 1 or 𝑡𝐴 𝒰, 1𝑡′𝑡′≥ 𝑝 ≤ Pr

（一般性を失わず𝑠 ≥ 𝑂 log 𝑛 としてよい。）

≥𝑝
𝒰, 1𝑡

′

∈ 𝐿 + Pr 𝑡𝐴 𝒰, 1𝑡

′

≥𝑝 ≤

1
+𝑜 1 .
4概要
1. 脱乱択化の理論• 理論の概要• 疑似乱数生成器の概念• 疑似乱数生成器の構成

2. メタ計算量と平均時計算量について• メタ計算問題• 平均時計算量• 最悪時・平均時計算量の同値性• 暗号との関係

𝐏 ≠ 𝐍𝐏予想と暗号の関係
𝐏 = 𝐍𝐏
任意の𝐍𝐏の問題が効率的に解けるor𝐏 ≠ 𝐍𝐏「フェルマーの最終定理の証明のうち、𝑛文字以内で記述できる証明を一つ見つけよ」という問題は（適切な定式化の下で）NPに属する。
効率的に解けない𝐍𝐏の問題が存在する

数学の証明を自動化できる

どのような公開鍵暗号でも効率的に解読可能
ビットコインが無価値になる（例：素因数分解）

安全な暗号が存在する（？）
公開鍵から秘密鍵を計算できる。
（一方向性関数が存在しないので、鍵生成の手順を逆方向に計算できる。）
公開鍵暗号方式を使うことにより、持ち主だけがコインを使えるようにしているImpagliazzoの５つの可能世界
Cryptomania

我々の知識と一貫性のある世界を5つに分類

Minicrypt

P ≠ NP
Pessiland

Heuristica

Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

Russell ImpagliazzoImpagliazzoの５つの可能世界
Cryptomania

我々の知識と一貫性のある世界を5つに分類

Minicrypt

P ≠ NP
Pessiland

任意の𝐍𝐏の最適化問題が高速に解ける。
証明が自動化できる。
安全な暗号は作れない。

Heuristica

Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

Russell ImpagliazzoImpagliazzoの５つの可能世界
Cryptomania

我々の知識と一貫性のある世界を5つに分類∃ 公開鍵暗号
Minicrypt∃ 秘密鍵暗号&∄ 公開鍵暗号DistNP ⊈ AvgP&

∄ 秘密鍵暗号&DistNP ⊆ AvgP

Pessiland（平均時計算量の意味でP ≠ NP）

HeuristicaP ≠ NP
Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

Russell ImpagliazzoImpagliazzoの５つの可能世界
Cryptomania∃ 公開鍵暗号

我々の知識と一貫性の難しい問題が存在するが、ある世界を5つに分類
安全な公開鍵暗号系が存在する。

∃ 秘密鍵暗号&∄ 公開鍵暗号DistNP ⊈ AvgP&

∄ 秘密鍵暗号&DistNP ⊆ AvgP

Minicrypt

Pessiland（平均時計算量の意味でP ≠ NP）

HeuristicaP ≠ NP
Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

Russell ImpagliazzoImpagliazzoの５つの可能世界
Cryptomania

我々の知識と一貫性のある世界を5つに分類∃ 公開鍵暗号
Minicrypt

考えられうる「最悪の世界」

暗号が作れない∄ 公開鍵暗号&
NPも簡単に解けない∃ 秘密鍵暗号（Pessimistic = 悲観的）

Pessiland

DistNP ⊈ AvgP
（平均時計算量の意味でP ≠ NP）&∄ 秘密鍵暗号&DistNP ⊆ AvgP

HeuristicaP ≠ NP
Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

Russell ImpagliazzoImpagliazzoの５つの可能世界
Cryptomania∃ 公開鍵暗号
Minicrypt

我々の知識と一貫性の最小限の暗号が作れる世界

ある世界を5つに分類
安全な秘密暗号方式が存在
公開鍵暗号方式は安全でない∃ 秘密鍵暗号&∄ 公開鍵暗号DistNP ⊈ AvgP&

∄ 秘密鍵暗号&DistNP ⊆ AvgP

Pessiland（平均時計算量の意味でP ≠ NP）

HeuristicaP ≠ NP
Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

Russell ImpagliazzoImpagliazzoの５つの可能世界
Cryptomania

Russell Impagliazzo

我々の知識と一貫性のある世界を5つに分類∃ 公開鍵暗号
Minicrypt∃ 秘密鍵暗号&∄ 公開鍵暗号

Pessiland

DistNP ⊈ AvgP
（平均時計算量の意味でP ≠ NP）

HeuristicaP ≠ NP

ヒューリスティクスが上手くいく世界∄ 秘密鍵暗号
多くの入力でNPが高速に解ける
安全な暗号は作れない&&

DistNP ⊆ AvgP

（平均時計算量の意味でP = NP）

Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

Impagliazzoの５つの可能世界
Cryptomania

Russell Impagliazzo

我々の知識と一貫性のある世界を5つに分類∃ 公開鍵暗号
Minicrypt∄ 公開鍵暗号∃計算量理論の究極的な使命
一方向性関数&我々の世界がどの世界であるかを決定すること！
Pessiland（特に、Cryptomaniaであるという予想を解決し、DistNP ⊈ AvgP
∄ 一方向性関数&（平均時計算量の意味でP≠NP）
絶対的に安全な暗号を確立すること。）

HeuristicaP ≠ NP&DistNP ⊆ AvgP

Algorithmica

P = NP
画像出展：https://www.simonsfoundation.org/people/russell-impagliazzo/

既知の事実と未解決問題?

Cryptomania∃ 公開鍵暗号
Minicrypt?

∃ 秘密鍵暗号?

Pessiland

DistNP ⊈ AvgP
（平均時計算量の意味でP ≠ NP）

Heuristica?

P ≠ NP
Algorithmica：既知の事実?

：重要な未解決問題

公開鍵暗号構築への道：既知の事実?

Cryptomania：重要な未解決問題∃ 公開鍵暗号
Minicrypt?

∃ 秘密鍵暗号?

Pessiland

重要な未解決問題

Minicryptを除外できるか？
重要な未解決問題

全ての矢印を証明⟺
我々の世界はCryptomania！

Pessilandを除外できるか？

DistNP ⊈ AvgP
（平均時計算量の意味でP ≠ NP）

Heuristica?

P ≠ NP
Algorithmica?

重要な未解決問題

Heuristicaを除外できるか？
重要な未解決問題
P ≠ NP予想（Algorithmicaを除外できるか？）

１つの矢印を証明⟺
１つの可能世界を除外

現在の証明手法の限界?

Cryptomania∃ 公開鍵暗号
Minicrypt?

ある種の証明手法ではその未解決問題を解決できない?
DistNP ⊈ AvgP

（平均時計算量の意味でP ≠ NP）

Heuristica

Algorithmica?

：重要な未解決問題：理論的な障壁∃ 秘密鍵暗号
Pessiland：既知の事実全ての矢印を証明⟺
我々の世界はCryptomania！

１つの矢印を証明⟺
相対化のバリア [Baker-Gill-Solovay’75]
１つの可能世界を除外

P ≠ NP

代数化のバリア?

自然な証明のバリア
局所性のバリア[Aaronson-Wigderson’09][Razborov-Rudich’97][Chen-H.-Oliveira-Pich-Rajgopal-Santhanam (ITCS’20)]

現在の証明手法の限界?

Cryptomania∃ 公開鍵暗号
Minicrypt：既知の事実?

：理論的な障壁
ある種の証明手法ではその未解決問題を解決できない∃ 秘密鍵暗号?

Pessiland

DistNP ⊈ AvgP
（平均時計算量の意味でP ≠ NP）

Heuristica?

P ≠ NP
Algorithmica?

相対化のバリア[Impagliazzo (2011)]
ブラックボックス帰着の限界[Feigenbaum & Fortnow (1993)][Bogdanov & Trevisan (2006)]
困難性増幅
の不可能性

[Viola (2005)]：重要な未解決問題

全ての矢印を証明⟺
我々の世界はCryptomania！
１つの矢印を証明⟺
１つの可能世界を除外

障壁を突破する➢ それぞれの障壁は乗り越えられる。

(MCSP, 𝒰) ∉ AvgBPP

Theorem [H. (FOCS 2018)]
GapMCSPの最悪時・平均時計算量は同値。

GapMCSP ∉ BPP[H. (FOCS 2018)]

ブラックボックス帰着[Bogdanov & Trevisan (2006)]の限界

UP ⊈ DTIME(2𝑂 𝑛/ log 𝑛 )困難性増幅の「不可能性」

NP ⊈ BPPDistNP ⊈ AvgP

[H. (STOC 2021)]

相対化のバリア

GapMCSP ∗ ∉ BPP[H. (FOCS 2022)]➢ 上手く組み合わせることができれば、原理的にはHeurisitcaが除外できる。

∗
MCSP (Partial MCSP; 部分関数版回路最小化問題)
入力

出力• 部分関数 𝑓: 0,1 𝑛 → 0, 1,∗ の
真理値表（𝑓 𝑥 =∗ なる入力𝑥は定義されていないとみなす。）• 閾値𝑠 ∈ ℕ

YES

例（∵ 𝐶 𝑥1 , 𝑥2 = 𝑥1 なる回路はゲート数0で𝑓を計算できる。）

• 𝑠=0

• 𝑓=

ゲート数𝑠以下の論理回路で入力𝑥 ∈ 𝑓 −1 0,1 において関数𝑓(𝑥)を出力するものが存在するかどうか。

𝒙𝟏

𝒙𝟐

𝒇(𝒙𝟏 , 𝒙𝟐 )定理 [H. (FOCS 2022)]

0

0

0

（乱択多項式時間帰着の下で）MCSP ∗ はNP完全。

0

1

∗

1

0

1

1

1

∗

➢ 招待講演：Oxford & Warwick (8月), Columbia (9月), UT Austin (11月), Oxford (11月)
Simons Institute (1月)
➢ Complexity result of the year 2022 受賞

∗
MINKT （部分関数版MINKT）
入力

出力• 部分文字列𝑥 ∈ 0,1,∗ 𝑛• 閾値𝑠 ∈ ℕ
• 時間パラメタ𝑡 ∈ ℕ（一進法で記述する）

ある文字列 𝑦 ∈ 0,1 𝑛 であって、𝑥と一貫性をもち、
K𝑡 𝑦 ≤ 𝑠となるものが存在するか？

Theorem [H. FOCS 2022]

GapMINKT ∗ は乱択多項式時間帰着の下でNP完全。
log 𝑛 Ω 1 倍近似問題➢ これをGapMINKTに拡張することができれば、Heuristicaを除外できる。

次のステップ：相対化のバリアの先へ
メタ計算量の世界[H.(FOCS 2018)]

Heuristicaの除外

DistNP ⊈ AvgBPP(MCSP, 𝒰) ∉ AvgBPP

GapMCSP ∉ BPP

ブラックボックス帰着[Feigenbaum-Fortnow’93]の限界[Bogdanov-Trevisan’06]?
[Impagliazzo’11][H. & Nanashima (FOCS’21)]

NP ⊈ BPP: 証明手法の限界?

相対化のバリア[Ko’91][H. (FOCS 2022)]

GapMCSP ∗ ∉ BPP

後半の参考文献➢ 平均時計算量のサーベイ
Andrej Bogdanov, Luca Trevisan, "Average-Case Complexity",Foundations and Trends in Theoretical Computer Science, 2006
➢ メタ計算量のサーベイ
Shuichi Hirahara, "Meta-Computational Average-Case Complexity: A
New Paradigm Toward Excluding Heuristica", Bull. EATCS, 2022

演習問題リスト
1.
2.
3.
4.
5.
6.
7.
8.

回路の上界
回路とコルモゴロフ記述量
直積生成器の安全性
組合せデザインの存在
貪欲法に基づく組合せデザインの構成
多項式に基づく組合せデザインの構成
Nisan-Wigderson疑似乱数生成器
AveMCSPに対する最悪時・平均時帰着--- 以下はおまけ --9. アダマール符号の復号
10. 誤りなしヒューリスティクスと平均時多項式時間アルゴリズム
11. 平均時多項式時間のロバスト性
12. GapMCSPの特徴付け

前書き：確率集中不等式（Chernoff bound）
以下のよく知られた確率集中不等式および非復元抽出への拡張を使ってよい。
数列Ω = Ω1 , ⋯ , Ω𝑁 ∈ 0,1 𝑁 から復元抽出で𝑛個選んだものを𝑋1 , … , 𝑋𝑛 とする。
（すなわち、各𝑋1 , … , 𝑋𝑛 ∈ {0,1}はベルヌーイ独立同一分布に従う。）
𝜇 ≔ 𝔼 σ𝑛𝑖=1 𝑋𝑖 とすると、任意の𝑡 > 0に対して、以下が成立する。
𝑛𝑡𝜇Pr ෍ 𝑋𝑖 ≥ 𝑡 ≤ exp −𝑡 ln
+ −1
𝜇
𝑡

.

𝑖=1

同様に、Ωから非復元抽出で𝑛個選んだものを𝑌1 , … , 𝑌𝑛 とすると、𝑛𝑡𝜇Pr ෍ 𝑌𝑖 ≥ 𝑡 ≤ exp −𝑡 ln
+ −1
𝜇
𝑡
𝑖=1

.

[Hoeffding 1963]

演習問題１：回路の上界
任意のブール値関数𝑓: 0,1 𝑛 → {0,1}がサイズ𝑂(2𝑛 ⋅ 𝑛)の回路で計算できることを証明せよ。

※ サイズ𝑂2𝑛𝑛の回路で計算できることが知られている。[Lupanov 1958]

演習問題２：回路とコルモゴロフ記述量
以下の事実を証明せよ。
1. あるチューリング機械𝑀が存在して、任意の𝑓 ∈ 0,1
K 𝑀 𝑓 = Θ CC 𝑓 log CC 𝑓 + 𝑛 .
2. 任意の機械𝑀について、

Pr 𝑁 K 𝑀 𝑥 ≥ 𝑛 − 2𝑥∼ 0,1

2𝑛

について、

3
≥ .
4

3. 一様ランダムなブール値関数𝑓: 0,1 𝑛 → {0,1}を取ると、高い確率でCC 𝑓 ≥ Ω

2𝑛
𝑛

となる。

演習問題３：直積生成器の安全性
1−𝜖2の誤りを訂正できるリスト復号可能誤り訂正符号Enc:ℓ = 𝑂 log𝑛
𝜖0,1 𝑛 →ℓ2
0,1 であって、となるようなものをとる。
ℓ 𝑘𝑘 ≤ 𝑛に対して、DP𝑘 : 0,1 × 0,1→ 0,1 ℓ𝑘+𝑘 を、DP𝑘 𝑥; 𝑧1 , … , 𝑧𝑘 = 𝑧1 , … , 𝑧𝑘 , Enc 𝑥 𝑧1 , … , Enc 𝑥 𝑧𝑘 と定める。
𝑛

文字列𝑥の𝐷オラクル時間制限付きコルモゴロフ記述量とは、最小の𝐷オラクル付きプログラムの長さをいう。正確には、
K𝑡,𝐷 𝑥 ≔ min 𝑑 ∶ 𝑈 𝐷 𝑑 が𝑡時間以内で𝑥を出力と定義される。
仮に関数𝐷: 0,1ℓ𝑘+𝑘→ {0,1}がDP𝑘 (𝑥; ⋅)を𝜖-識別するとき、十分大きい𝑡 =𝑛𝑡,𝐷K𝑥 ≤ 𝑘ℓ + 𝑘 + 𝑂 log𝜖であることを証明せよ。

𝑛 𝑂(1)
について、𝜖演習問題３の補遺
特に、対偶をとると、
K𝑡,𝐷 𝑥 > 𝑘ℓ + 𝑘 + 𝑂 log 𝑛/𝜖となる。

ならば Pr 𝐷 𝐷𝑃𝑘 𝑥; 𝑧𝑧

= 1 − Pr 𝐷 𝒰 = 1 ≤ 𝜖
𝒰

実はE ⊈ ‫>𝛼ځ‬0 io−SIZE 2𝛼𝑛 の下で、𝑘ℓ + 𝑘 を 𝑘まで改善できる。具体的には：𝑛

任意のpoly
サイズ回路𝐷: 0,1 𝑘ℓ+𝑘 → {0,1}に対して、
𝜖
もし𝐷がDP𝑘 (𝑥; ⋅)を𝜖-識別するのであれば、
K𝑡,𝐷 𝑥 ≤ 𝑘 + 𝑂 log 𝑛/𝜖 .
さらに、DistNP ⊆ AvgP ⟹ E ⊈ ‫>𝛼ځ‬0 io−SIZE 2𝛼𝑛 である。[Buhrman-Fortnow-Pavan’05]
これを用いて、DistNP ⊆ AvgP ならば GapMINKT ∈ Pを示せる。[H. CCC’20]

演習問題４：組合せデザインの存在
𝑑, ℓ, 𝜌 -組合せデザイン（combinatorial design）とは、
𝑑 = {1, … , 𝑑}上の集合族{𝑆1 , … , 𝑆𝑚 }であって、以下の条件を満たすものをいう。
• 任意の𝑖 ∈ [𝑚]について、 𝑆𝑖 = ℓ• 相異なる𝑖, 𝑗 ∈ [𝑚]について、 𝑆𝑖 ∩ 𝑆𝑗 ≤ 𝜌ℓ2
𝑑 = ⋅ exp
𝜌

2 ln 𝑚1+
𝜌

のとき、(𝑑, ℓ, 𝜌)-組合せデザインが存在することを証明せよ。

演習問題５：貪欲法に基づく組合せデザインの構成
次のアルゴリズムによって(𝑑, ℓ, 𝜌)-組合せデザイン𝑆1 , … , 𝑆𝑚 を構築する。
For 𝑖 = 1, … , 𝑚:

For 𝑆𝑖 ∈𝑑ℓ:

If 𝑆𝑖 ∩ 𝑆𝑗 ≤ 𝜌 for every 𝑗 ∈ 1, … , 𝑖 − 1 :break# 次の𝑖へOutput (𝑆1 , … , 𝑆𝑚 )任意の定数𝛾 > 0に対し、ある定数𝑐 ∈ ℕが存在し、
𝑑 = 𝑐ℓ, 𝜌 = 𝛾ℓ, 𝑚 = 2ℓとしたとき、上述のアルゴリズムは2𝑂(ℓ) 時間で(𝑑, ℓ, 𝜌)-組合せデザインを正しく計算することを示せ。

演習問題６：多項式に基づく組合せデザインの構成ℓを素数として、体ℤℓ 上の𝜌次1変数多項式𝑔 ∈ ℤℓ 𝑋 を考えると、
根は高々𝜌個である。この事実を用いて、(𝑑, ℓ, 𝜌)-組合せデザインを構成しよう。
𝑔1 , … , 𝑔2𝜌+1 ∈ ℤℓ 𝑋 を係数が0か1の𝜌次多項式を辞書順に並べたものとする。
各多項式𝑔𝑖 を用いて集合𝑆𝑖 ⊆ 𝑑 を上手く定義することにより、(𝑑 = 𝑂 ℓ2 , ℓ, 𝜌)-組合せデザイン𝑆1 , … , 𝑆2𝜌+1 を構成せよ。

演習問題７：Nisan-Wigderson疑似乱数生成器
𝑑, 𝑛, 𝜌 -組合せデザイン𝑆1 , … , 𝑆𝑚 を固定する。
ℎ: 0,1 𝑛 → 0,1 に対し、NWℎ (𝑧)は次のように定義される。
0,1 𝑚

∈

NWℎ : 0,1 𝑑 →𝑧↦ℎ 𝑧𝑆1 ⋯ ℎ(𝑧𝑆𝑚 )ここで、 大きさ𝑛の集合𝑆 = 𝑖1 < ⋯ < 𝑖𝑛 ⊆ [𝑑]に対し、𝑧𝑆 ≔ 𝑧𝑖1 ⋯ 𝑧𝑖𝑛 と定める。
以下を証明せよ。

1. サイズ𝑚の回路𝐷がNWℎ (⋅)を𝛿-識別するならば、
𝛿𝜌෫ℎ ∈ SIZE 𝑂 𝑚 ⋅ 2 ⋅ 𝜌 ;.
𝑚
2. E ⊈ ‫>𝜖ځ‬0 io−S෫
IZE 2𝜖𝑛 ; 2−𝜖𝑛 ⟹ P = BPP.

ℎNisan-Wigderson疑似乱数生成器 NW• 計算困難関数ℎ: 0,1 𝑛 → 0,1• 疑似乱数生成器NW : 0,1
ℎ

𝑗11

𝑗12

→ 0,1

2𝜖𝑛

𝑗13

𝑧 ∈ 0,1 𝑂 𝑛

乱数の種 𝑧

𝑆1

𝑆2

𝑧𝑆1

𝑧𝑆2

∈ 0,1 𝑛𝑆3𝑧𝑆3 𝑧𝑆4 …

𝑧𝑆1 = 𝑧𝑗11 𝑧𝑗12 𝑧𝑗13↦ℎ(𝑧𝑆1 ) ℎ(𝑧𝑆2 )∈ {0,1}𝑆1 = 𝑗11 < 𝑗12 < 𝑗13(𝑛 = 3)

↦

↦

出力

𝑂(𝑛)

相異なる𝑖 ≠ 𝑗 ∈ {1, … , 𝑚}に対して
𝑆𝑖 ⊆ 1, … , 𝑂 𝑛 , 𝑆𝑖 ∩ 𝑆𝑗 ≤ 𝜖𝑛.

ℎ(𝑧𝑆3 )…

ℎ=: NW 𝑧 ∈ 0,12𝜖𝑛演習問題８：AveMCSPの最悪時・平均時帰着
多項式𝑝に対して、約束付き問題Ave𝑝 MCSPを次のように定める。

Ave𝑝 MCSPYES ≔𝑓, 𝑠𝑓 ∈ SIZE 𝑠

=

𝑓, 𝑠

Ave𝑝 MCSPNO ≔𝑓, 𝑠𝑓 ∉ S෫
IZE 𝑝(𝑠, 𝑛);

CC 𝑓 ≤ 𝑠 ,1𝑝(𝑠, 𝑛)DistNP ⊆ AvgP ならば、ある多項式𝑝が存在して、Ave𝑝 MCSP ∈ Pであることを証明せよ。

𝑛. （ただし、𝑓 ∈ 0,1 2 ）演習問題９：アダマール符号の局所復号
アダマール符号Had: 0,1

𝑛

→ 0,1

2𝑛

は、任意の𝑟 ∈ 0,1 𝑛 について𝑛

Had 𝑥 𝑟 ≔ ෍ 𝑥𝑖 𝑟𝑖として定義される。

mod 2

𝑖=1

問：オラクル付き乱択多項式時間アルゴリズムDecであって、𝑛任意の𝑓 ∈ 0,1 2 であってPr 𝑛 𝑓 𝑥 𝑟 = Had 𝑥 𝑟 > 0.76
𝑟∼ 0,1なるものに対し、Pr Dec 𝑓 1𝑛 = 𝑥 ≥ 0.999
DecであるDecを構成せよ。
1※ アダマール符号は 2 − 𝜖 の誤りから局所リスト復号可能であることが知られている。[Goldreich-Levin’89]

演習問題１０：誤りなしヒューリスティクス➢ 平均時多項式時間AvgPは誤りなしヒューリスティクスを用いて(errorless heuristics)
特徴づけることができる。
事実 次は同値。
1. 𝐿, 𝒟 ∈ AvgP

アルゴリズムの失敗⟺
計算時間が超多項式時間（計算を打ち切る）

2. あるアルゴリズム𝐴であって、以下の条件を満たすものが存在する。
（𝐴: 誤りなしヒューリスティクス）(a) 𝐴 𝑥; 𝛿, 𝑛 ∈ 𝐿 𝑥 , “失敗” （アルゴリズムは正しい答えを返す or 失敗）(b) Pr 𝐴 𝑥; 𝛿, 𝑛 = "失敗" ≤ 𝛿 （アルゴリズムの失敗確率は𝛿以下）𝑥∼𝒟𝑛(c) 𝑡𝐴 𝑥; 𝛿, 𝑛 ≤ poly 𝑛/𝛿 （アルゴリズムの実行時間は多項式時間）

演習問題１１：平均時多項式時間のロバスト性ある関数𝑡: 0,1 𝑛 → ℕであって、
1. 𝔼𝑥∼ 0,1 𝑛 𝑡 𝑥≤ 𝑛 であるが、2. 𝔼𝑥∼ 0,1 𝑛 𝑡 𝑥 2 ≥ 2𝑛 となるものが存在することを証明せよ。
※ 従って、期待多項式時間を𝔼𝑥∼ 0,1 𝑛 𝑡 𝑥 ≤ 𝑛𝑂(1) として定義すると、計算モデル（チューリング機械やRAM）に依存した定義になってしまう。

演習問題１２：GapMCSPの特徴付け
以下の条件の同値性を示せ。
1. ある定数𝜖 > 0について、Gap𝜖 MCSP ∈ P。
2. ある定数𝜖 > 0と多項式時間アルゴリズム𝐴が存在し、CC 𝑓 ≤ 𝐴 𝑓 ≤ CC 𝑓 ⋅ 2 1−𝜖 𝑛を満たす。

あとがき：暗号的疑似乱数生成器との関係• ≈𝑐 の記号は非標準的な使い方であることを注意しておく。 𝑋 ≈𝑐 𝑌は暗号の文脈でよく使われる。
• 任意の多項式サイズ回路について𝑋と𝑌が識別不可能なとき、𝑋 ≈𝑐 𝑌と書く。
（線形サイズ回路に対する識別不可能性ついては、普通この記号を用いない。）• 暗号学的疑似乱数生成器𝐺は、
統計的テストの計算時間 ≫ 𝐺の計算時間であるようなもの。一方向性関数の存在と同値 [Hastad-Impagliazzo-Levin-Luby’99]。
• 本講演で扱ったものは計算量理論的疑似乱数生成器𝐺で、統計的テストの計算時間 ≪ (𝐺の計算時間)。