Limits of Minimum Circuit
Size Problem as Oracle(CCC 2016)
平原 秀一（東京大学、ERATO研究協力者）
渡辺 治（東京工業大学）

ERATO感謝祭 SeasonⅢ

2016/8/10

概要: 回路最小化問題はNP完全か？
(Minimum Circuit Size Problem; MCSP)

入力

真理値表𝒙𝟏𝒙𝟐𝒙𝟏 xor 𝒙𝟐000011101110

出力

回路サイズ = 5∨∧∧

¬

¬
𝑥1𝑥2

我々の貢献

“現在の帰着手法”では回路最小化問題のNP完全性を示せない、ということに対して強い証拠を与えた。

目次
1. 問題設定・重要性
2. 背景・先行研究
MCSPの二つの側面

3. “オラクル独立”帰着
なぜ現在の帰着手法はオラクル独立なのか

4. 結果・まとめ目次
1. 問題設定・重要性
2. 背景・先行研究
MCSPの二つの側面

3. “オラクル独立”帰着
なぜ現在の帰着手法はオラクル独立なのか

4. 結果・まとめ回路最小化問題(MCSP)
入力𝒙𝟏𝒙𝟐00
加えて、サイズパラメタ0 𝑠∈ℕ1

真理値表𝑇

出力

∨ サイズ≤ 𝒔以下

𝒙𝟏 xor 𝒙𝟐0∧

1101110

回路サイズ = 5ならばYES

∧¬

¬

𝑥1𝑥2

定義 (回路最小化問題; Minimum Circuit Size Problem; MCSP)
𝑛20, 1と サイズパラメタ 𝑠 ∈ ℕ

入力: 真理値表 𝑇 ∈出力: 真理値表を実現するサイズ𝑠以下の回路が存在するか？
注意: 入力に対して多項式時間 ⇔ 2𝑂(𝑛) 時間

MCSPはNPに属する
 NPの証拠: サイズ𝑠以下の回路𝐶
 証拠の正しさのチェック:全てのありうる入力𝑥1 , … , 𝑥𝑛 を試して真理値表𝑇と一致するか確かめる。
 2𝑂 𝑛 時間・・・ 入力長2𝑛 について多項式時間

定義 (回路最小化問題; Minimum Circuit Size Problem; MCSP)
𝑛20, 1と サイズパラメタ 𝑠 ∈ ℕ

入力: 真理値表 𝑇 ∈出力: 真理値表を実現するサイズ𝑠以下の回路が存在するか？
注意: 入力に対して多項式時間 ⇔ 2𝑂(𝑛) 時間

問:
問 MCSPはどのくらい難しいのか？
NP完全か？
MCSPが解ける ⟹ SATが解ける？
MCSP ∈ coNPか？

coNP

NPP

重要性:
重要性 MCSPの計算量理論的側面• NPに対する回路下界計算量理論のゴールのひとつ:

NP ⊈ SIZE(𝑛𝑂 1 )⟹P ≠ NP多項式サイズの回路で解ける問題全体• MCSPと回路下界は深く関連している。

MCSP ∈ P⟹

EXPNP ⊈ SIZE(𝑛𝑂 1 )[Kabanets & Cai (2000)]

もし示せれば大きなブレークスルー

重要性:
重要性 MCSPの計算量理論的側面• NPに対する回路下界計算量理論のゴールのひとつ:

NP ⊈ SIZE(𝑛𝑂 1 )⟹P ≠ NP多項式サイズの回路で解ける問題全体• MCSPと回路下界は深く関連している。

MCSP ∈ P⟹

EXPNP ⊈ SIZE(𝑛𝑂 1 )[Kabanets & Cai (2000)]MCSP ∈ coNP ⟹ EXPNP ⊈ SIZE(𝑛𝑂 1 )目次
1. 問題設定・重要性
2. 背景・先行研究
MCSPの二つの側面

3. “オラクル独立”帰着
なぜ現在の帰着手法はオラクル独立なのか

4. 結果・まとめ背景: MCSPの二つの側面
一般的な帰着[Allender & Das (2014)]• MCSPはBPP帰着の下でSZK困難

制限された帰着の下ではNP完全性を示すのが難しい≤BPP
𝑇

一般的な帰着の下では困難性を示せる[Murry & Williams (2015)]• 多対一帰着の下ではNP完全性を示すことが難しい

𝑝≤𝑚

制限された帰着

帰着の種類 (1/3)
定義 (多対一帰着; カープ帰着)
SATがMCSPに多対一帰着できる⟺ ある多項式時間機械𝑀があって、MCSP 𝑀 𝜑= SAT 𝜑 .

機械𝑀で多項式時間で変換可能

SATのインスタンス
論理式𝜑𝜑が充足可能⟼⟺

MCSPのインスタンス
𝑇, 𝑠
真理値表𝑇を実現する
サイズ𝑠以下の回路が存在する

 NP完全性を議論するときの普通の帰着の概念

帰着の種類 (2/3)
定義 (P帰着;多項式時間チューリング帰着; クック帰着)
SATがMCSPにP帰着できる (SAT ∈ P MCSP )⟺ ある多項式時間オラクル機械𝑀があって、𝑀MCSP 𝜑 = SAT 𝜑 .
つまり、MCSPが単位時間で解ける⟹ SATが多項式時間で解ける対偶をとるとSATが難しい 多対一帰着の一般化⟹MCSPも難しい

帰着の種類 (3/3)(Bounded-error Probabilistic Polynomial)

定義 (BPP帰着)
SATがMCSPにBPP帰着できる (SAT ∈ BPP MCSP )⟺ ある多項式時間乱択オラクル機械𝑀があって、𝑀MCSP 𝜑 = SAT 𝜑が99%以上で成立する。
つまり、MCSPが単位時間で解けると仮定して、SATが乱択アルゴリズムで多項式時間で計算できる。

背景: MCSPの困難性[Allender, Buhrman, Koucký, van Melkebeek and Ronneburger (2006)]• 素因数分解がMCSPにBPP帰着できる（素因数分解∈ BPP MCSP ）• 離散対数問題がMCSPにBPP帰着できる（離散対数問題 ∈ BPP MCSP ）離散対数問題

coNP

素因数分解

PNP

NPの中間の問題より
困難

問:問 MCSPはどのくらい難しいのか？
MCSPはPには属さない（素因数分解が簡単でない限り）（注） 素因数分解 ∈ NP ∩ coNP

coNP

素因数分解

PNP

背景: MCSPの困難性[Allender & Das (2014)]
統計的ゼロ知識証明(SZK)の任意の問題がMCSPにBPP帰着できる。
(Statistical Zero Knowledge)

つまり、 SZK ⊆ BPP MCSP

離散対数問題

coNP

素因数分解

P

SZK

NP

MCSPは
SZK困難

制限された帰着では困難性を示すことは難しい[Murray & Williams (CCC 2015)]• 多対一帰着の下でNP完全性を示せたとすると、重要な未解決問題(ZPP ≠ EXP)が従う。
多対一帰着の下でNP完全性を示すのは難しい。

背景: MCSPの二つの側面
一般的な帰着[Allender & Das (2014)]• MCSPはBPP帰着の下でSZK困難≤BPP
𝑇

一般的な帰着の下では困難性を同様の手法で示せる制限された帰着の下NP困難性を示せるか？
ではNP完全性を示すのが難しい[Murry & Williams (2015)]• 多対一帰着の下ではNP完全性を示すことが難しい

𝑝≤𝑚

制限された帰着背景: MCSPの二つの側面
一般的な帰着[Allender & Das (2014)]• MCSPはBPP帰着の下でSZK困難≤BPP𝑇

一般的な帰着な下では困難性を
1. 「現在の帰着手法」ではP帰着の下でもNP完全性示せる制限された帰着の下を示せない。
ではNP完全性を示す
2. 同様に（クエリが一回の）BPP帰着の下でも示せない。のが難しい
我々の結果≤BPP𝑚𝑝≤𝑇[Murry & Williams (2015)]• 多対一帰着の下ではNP完全性を示すことが難しい

𝑝≤𝑚

制限された帰着

目次
1. 問題設定・重要性
2. 背景・先行研究
MCSPの二つの側面

3. “オラクル独立”帰着
なぜ現在の帰着手法はオラクル独立なのか

4. 結果・まとめ

オラクル回路最小化問題• Aをオラクルとする。 𝐴 ∶ 0, 1 ∗ → 0,1
定義 (𝑨オラクル回路最小化問題; 𝐌𝐂𝐒𝐏 𝑨 )𝑛20, 1と サイズパラメタ 𝑠 ∈ ℕ

入力: 真理値表 𝑇 ∈出力: 真理値表を実現するサイズ𝑠以下の𝐴オラクル回路が存在するか？
𝐴 𝑥1 , … , 𝑥4

∨ ∧ ¬ の他にオラクルゲート 𝐴が使える

𝐴𝑥1 𝑥2 𝑥3 𝑥4

オラクル独立帰着
アイディア:帰着が（MCSPの性質というよりも）全てのMCSP 𝐴 に共通の性質だけしか使っていない。
定義 (オラクル独立帰着)

問題Lが、任意のオラクル𝐴に対して、MCSP 𝐴 へ帰着できるとき、𝐿はMCSPにオラクル独立帰着できるという。
例えば:問題𝐿がMCSPにオラクル独立P帰着できる
def⟺⟺

𝐴
MCSP
任意のオラクル𝐴に対して𝐿 ∈ P𝐴MCSPP.

𝐿∈𝐴

現在の帰着手法は全てオラクル独立• Allender & Das (2014)の結果はオラクル独立帰着になっている

MCSPはBPP帰着の下でSZK困難:SZK ⊆ BPPMCSP（一般化）

MCSPはオラクル独立BPP帰着の下でSZK困難:SZK ⊆BPP
𝐴• 他の帰着も全てオラクル独立

MCSP𝐴

Let’s lookat it.

MCSPを用いてSZKを解く
主張:

SZK ⊆ BPPMCSP[Allender & Das (2014)]

重要な観察

任意の疑似乱数生成器がMCSPを用いて破れる。

⟹[Hastad, Impagliazzo, Levin & Luby (1999)]

任意の一方向性関数が破れる⟹[Allender & Das (2014)]

SZKが多項式時間で解ける

MCSPを用いて疑似乱数生成器を破る
重要な観察

任意の疑似乱数生成器がMCSPを用いて破れる。
（出力を真理値表だとみなすと）疑似乱数生成器の出力 𝐺 𝑟← 回路計算量が低い

MCSPを用いると二つの文字列を区別できる
一様ランダムに選ばれた文字列← 回路計算量は高い

MCSPを用いて疑似乱数生成器を破る
重要な観察

任意の疑似乱数生成器がMCSPを用いて破れる。
（出力を真理値表だとみなすと）

疑似乱数生成器の出力 𝐺 𝑟← 回路計算量が低い• 疑似乱数生成器は“効率的に”計算可能なので、回路計算量も低い
一様ランダムに選ばれた文字列← 回路計算量は高い• 数え上げの議論より、高い確率で回路計算量は高い
サイズ𝑠以下の回路は高々𝑠 𝑂(𝑠) 個程度
𝑛
一方、長さ2𝑛 の真理値表は22 程度

𝐴

MCSP を用いて疑似乱数生成器を破る
重要な観察

任意の疑似乱数生成器がMCSP 𝐴 を用いて破れる。
（出力を真理値表だとみなすと）

疑似乱数生成器の出力 𝐺 𝑟← 回路計算量が低い• 疑似乱数生成器は“効率的に”計算可能なので、回路計算量も低い
オラクルゲートが使える状況でも回路サイズは小さいまま
一様ランダムに選ばれた文字列← 回路計算量は高い• 数え上げの議論より、高い確率で回路計算量は高い
サイズ𝑠以下の回路は高々𝑠 𝑂(𝑠) 個程度
数え上げの議論はそのまま成立
𝑛𝑛
一方、長さ2 の真理値表は22 程度

𝐴

MCSP を用いて疑似乱数生成器を破る
重要な観察

任意の疑似乱数生成器がMCSP 𝐴 を用いて破れる。
（出力を真理値表だとみなすと）← 回路計算量が低い

疑似乱数生成器の出力 𝐺 𝑟• 疑似乱数生成器は“効率的に”計算可能なので、系 回路計算量も低い[Allender & Das (2014)]

SZK ⊆オラクルゲートが使える状況でも回路サイズは小さいまま
𝐴MCSP

BPP

一様ランダムに選ばれた文字列
𝐴.

← 回路計算量は高い• 数え上げの議論より、高い確率で回路計算量は高い
サイズ𝑠以下の回路は高々𝑠 𝑂(𝑠) 個程度
数え上げの議論はそのまま成立
𝑛𝑛
一方、長さ2 の真理値表は22 程度

なぜオラクル独立帰着しか知られていないのか？
一般に、具体的な関数の回路下界を得るのは非常に難しい。
• 例えば、EXP NP ⊈ SIZE(𝑛𝑂 1 )かどうかは未解決。

回路下界として数え上げの議論しか使っていない「一様ランダムに選んだ（具体的でない）関数は高い回路計算量を持つ。」

任意のオラクル𝐴をつけても成立する議論

目次
1. 問題設定・重要性
2. 背景・先行研究
MCSPの二つの側面

3. “オラクル独立”帰着
なぜ現在の帰着手法はオラクル独立なのか

4. 結果・まとめ我々の結果 (1/2)
定理 1. (オラクル独立P帰着の限界)

問題𝐿がMCSPにオラクル独立P帰着したとすると、𝐿はPに属する。別の言い方をすると、
𝐴

P MCSP = P.
𝐴

特に、MCSPはその帰着の下ではNP困難ではない。
（P = NPでない限り）

我々の結果 (2/2)
定理 2. (オラクル独立BPP帰着の限界)

問題𝐿がMCSPに（クエリが一回の）オラクル独立BPP帰着したとすると、 𝐿はAM ∩ coAMに属する。
別の言い方をすると、
𝐴 [1]
MCSP
BPP
⊆ AM ∩ coAM.

𝐴

特に、MCSPはその帰着の下ではNP困難ではない。
（多項式階層がつぶれないかぎり）AMとは（Arthur-Merlin）• AM = BP ∙ NP

AMcoAM• SZK ⊆ AM ∩ coAM
[Fortnow ’87]
[Aiello & Hastad ‘91]

coNP

NP
P

SZK

• 多項式階層がつぶれないかぎり、NP ⊈ coAM（特に、NP ⊈𝐴

𝐴 [1]
MCSP
BPP）

AMとは（Arthur-Merlin）
オラクル独立BPP帰着できる範囲• AM = BP ∙ NP

AMcoAM• SZK ⊆ AM ∩ coAM
[Fortnow ’87]
[Aiello & Hastad ‘91]

coNP

NPP

SZK

• 多項式階層がつぶれないかぎり、NP ⊈ coAM
（特に、NP ⊈𝐴

𝐴 [1]MCSPBPP）

まとめ• 我々の貢献
1. MCSPの帰着の限界を議論する枠組みを導入（オラクル独立帰着）
2. P帰着でも（クエリが一回の）BPP帰着でもNP完全性を示せないことを示した。
難しさの本質 = 回路下界を得るのが難しい。
• 数え上げの議論だけの回路下界ではオラクル独立帰着になってしまう。

• 未解決問題
より強い帰着ではどうか？NP ⊆ coNP MCSP ？
複数回のクエリがあったときにも限界を示せるか？