回路最小化問題の平均計算量について(CCC 2017)
平原秀一

東京大学 博士課程2年
ERATO研究協力者
共同研究者： Rahul Santhanam (University of Oxford)
ERATO感謝祭 Season IV

2017年8月4日

目次
1. 回路最小化問題（MCSP）について
2. 平均計算量とは
3. 自然な証明について
4. MCSPの最悪計算量から平均計算量への帰着について（疑似ランダム自己帰着性）

目次
1. 回路最小化問題（MCSP）について
2. 平均計算量とは
3. 自然な証明について
4. MCSPの最悪計算量から平均計算量への帰着について（疑似ランダム自己帰着性）

論理回路• 論理回路は論理ゲートを組み合わせて構成される
ORゲート

ANDゲート NOTゲート

𝑥1 ∨ 𝑥2

𝑥1 ∧ 𝑥2

¬𝑥∨

∧

¬

𝑥1

𝑥2

𝑥1𝑥2𝑥

https://en.wikipedia.org/wiki/VLSI_Technology

論理回路• 論理回路は論理ゲートを組み合わせて構成される

例: 2入力XORを計算する回路

𝑥1 ⊕ 𝑥2∨ORゲートANDゲート NOTゲート∧∧

𝑥1 ∨ 𝑥2

𝑥1 ∧ 𝑥2

¬𝑥∨

∧¬¬𝑥2
1
https://en.wikipedia.org/wiki/VLSI_Technology

𝑥1𝑥2

𝑥1𝑥2

¬𝑥𝑥

論理回路
• 論理回路は論理ゲートを組み合わせて構成される

例: 2入力XORを計算する回路

𝑥1 ⊕ 𝑥2∨ORゲートANDゲート NOTゲート∧∧

𝑥1 ∨ 𝑥2

𝑥1 ∧ 𝑥2

¬𝑥∨

∧

¬

¬

𝑥2
1
https://en.wikipedia.org/wiki/VLSI_Technology

𝑥1𝑥2

𝑥1𝑥2

¬𝑥𝑥

➢ 出来る限り小さいサイズ（ゲート数）の回路を求めたい。
➢ コンピュータで自動的にそのような回路を求めたい。

回路最小化問題（Minimum Circuit Size Problem; MCSP）
入力出力実現したい関数
𝑓: 0,1 𝑛 → {0, 1}の真理値表と自然数𝑠 ∈ ℕ

関数𝑓を計算するサイズ𝑠以下の回路が存在するか？

（入力例）
𝑠=5𝑓=（出力）“YES”

𝒙𝟏𝒙𝟐𝒙𝟏 ⊕ 𝒙𝟐000011101110(実際にXORを計算する
右図のような回路が存在するので。)

回路最小化問題（Minimum Circuit Size Problem; MCSP）
入力

出力

実現したい関数
𝑓: 0,1 𝑛 → {0, 1}の真理値表と自然数𝑠 ∈ ℕ

関数𝑓を計算するサイズ𝑠以下の回路が存在するか？

（入力例）
𝑠=5𝑓=0

（出力）

“YES”

𝒙𝟏𝒙𝟐𝒙𝟏 ⊕ 𝒙𝟐0000111011100(実際にXORを計算する
右図のような回路が1存在するので。)

0100

回路最小化問題（Minimum Circuit Size Problem; MCSP）
入力

出力

実現したい関数
𝑓: 0,1 𝑛 → {0, 1}の真理値表と自然数𝑠 ∈ ℕ

関数𝑓を計算するサイズ𝑠以下の回路が存在するか？

（入力例）
𝑠=5

𝑓=1

（出力）

“YES”

𝒙𝟏𝒙𝟐𝒙𝟏 ⊕ 𝒙𝟐000011101110(実際にXORを計算する右図のような回路が1存在するので。)

10001

Cook-Levinの定理 (1970s)

CookLevin

NPの問題の中で最も難しい。

定理 (Cook-Levin)

充足可能性問題(SAT)はNP完全である。

➢ 𝐏 vs 𝐍𝐏問題の発端となった定理

Cook-Levinの定理 (1970s)
MCSPの計算量について何かを言いたいなあ…

CookLevin

定理 (Cook 1971, Levin 1973)

充足可能性問題(SAT)はNP完全である。

➢ 𝐏 vs 𝐍𝐏問題の発端となった定理

Cook-Levinの定理 (1970s)

Levin

定理 (Cook 1971, Levin 1973)
Kolmogorov
早く結果を（指導教官）
充足可能性問題(SAT)はNP完全である。
出版しなさい！

➢ 𝐏 vs 𝐍𝐏問題の発端となった定理

Cook-Levinの定理 (1970s)

わかりました。
でも2ページだけ定理 (Cook 1971, Levin 1973)
Kolmogorovの論文で！
早く結果を（指導教官）
充足可能性問題(SAT)はNP完全である。
出版しなさい！
Levin➢ 𝐏 vs 𝐍𝐏問題の発端となった定理

重要な未解決問題

MCSPはNP完全か？
SAT
MCSP?

• NP完全だと予想している人もいるし、coNP• NPの中間の問題だと予想している人もいる。
（多項式時間では解けないがNP完全でもない問題のこと）

素因数分解

PNP

重要な未解決問題

MCSPはNP完全か？
SAT• NP完全だと予想している人もいるし、MCSP?

coNP• NPの中間の問題だと予想している人もいる。
（多項式時間では解けないがNP完全でもない問題のこと）

素因数分解

PNP

重要な未解決問題

MCSPはNP完全か？
SAT• NP完全だと予想している人もいるし、MCSP?

coNP• NPの中間の問題だと予想している人もいる。
（多項式時間では解けないがNP完全でもない問題のこと）

素因数分解

PNP

目次
1. 回路最小化問題（MCSP）について
2. 平均計算量とは
3. 自然な証明について
4. MCSPの最悪計算量から平均計算量への帰着について（疑似ランダム自己帰着性）

平均計算量とは➢ 最悪計算量：アルゴリズムが最も悪く振る舞うような入力における計算量のこと。

➢ 平均計算量：入力がある分布から生成されているとしたときに、高い確率で正しく計算するアルゴリズムの計算量。
（アルゴリズム自体は決定性でもよい）例：Random 3SAT [Feige 2002]➢ 3SATの平均計算量版➢ 3CNF式の各節が一様ランダムに生成される。
➢ 変数の数は𝑛、節の数は𝑂 𝑛 。

𝜑 = 𝑥1 ∨ 𝑥3 ∨ 𝑥4 ∧ 𝑥2 ∨ 𝑥3 ∨ 𝑥4 ∧ 𝑥1 ∨ 𝑥2 ∨ 𝑥4
定義：Random 3SATを解くアルゴリズム

Random 3SATを解くアルゴリズムとは、(1) 充足可能なすべての式を受理し、(2) 充足不能なすべての式を拒否するようなもの。

例：Random 3SAT [Feige 2002]➢ 3SATの平均計算量版➢ 3CNF式の各節が一様ランダムに生成される。
➢ 変数の数は𝑛、節の数は𝑂 𝑛 。

𝜑 = 𝑥1 ∨ 𝑥3 ∨ 𝑥4 ∧ 𝑥2 ∨ 𝑥3 ∨ 𝑥4 ∧ 𝑥1 ∨ 𝑥2 ∨ 𝑥4
定義：Random 3SATを解くアルゴリズム

Random 3SATを解くアルゴリズムとは、(1) 充足可能なすべての式を受理し、(2) 充足不能な多くの式（例えば全体のうち50%の式）を拒否するようなもの。

回路最小化問題の平均計算量➢ サイズパラメタ𝑠 ∈ ℕを入力から除く。
➢ 代わりに、𝑠: ℕ → ℕを事前に決めておき、MCSP s を考える。
定義：MCSP[s] (Parameterized version of MCSP)

入力

出力実現したい関数
𝑓: 0,1 𝑛 → {0, 1}の真理値表（＝2𝑛 の長さの文字列）と自然数𝑠 ∈ ℕ

関数𝑓を計算するサイズ𝑠 𝑛以下の回路が存在するか？

➢ 入力の分布は𝑓: 0,1 𝑛 → 0,1 の一様分布を考える。

回路最小化問題の平均計算量➢

ただし、YESとなる入力はとても少ないので、ゼロ誤りアルゴリズムを考える。 YESインスタンスの数 = 𝑠 𝑂 𝑠 ≪ 全体のインスタンスの数 = 22𝑛

定義：ゼロ誤りアルゴリズム
ゼロ誤りアルゴリズムとは、(1) “1”, “0”, “?”のどれかを出力し、(2) “?”と出力する割合は全体の50%以下であって、(3) YESの入力に対しては“1”か“?”と出力し、(4) NOの入力に対しては“0”か“?”と出力するようなもの。

MCSP 𝑠 の入力全体

YES

NOインスタンス
サイズ𝑠 𝑛 以下の回路で計算できない関数

回路最小化問題の平均計算量➢

ただし、YESとなる入力はとても少ないので、ゼロ誤りアルゴリズムを考える。 YESインスタンスの数 = 𝑠 𝑂 𝑠 ≪ 全体のインスタンスの数 = 22𝑛

定義：ゼロ誤りアルゴリズム
ゼロ誤りアルゴリズムとは、(1) “1”, “0”, “?”のどれかを出力し、(2) “?”と出力する割合は全体の50%以下であって、(3) YESの入力に対しては“1”か“?”と出力し、(4) NOの入力に対しては“0”か“?”と出力するようなもの。

MCSP 𝑠 の入力全体‘1’YES‘?’ ‘0’NOインスタンス

サイズ𝑠 𝑛 以下の回路で計算できない関数

回路最小化問題の一種の困難性定理• 時間制限付きコルモゴロフ記述量KTの最小化問題。
• 回路の代わりに、Random Access Machineの計算時間＋プログラムの長さを最小化する問題。

MKTP[𝑠]（回路最小化問題MCSPの一種）はRandom 3SAT困難。（∃𝑠: ℕ → ℕ）
証明のアイディア：Identity Mapが帰着を与える。
Ryan O’Donnellの予想

Random 3SATは（多項式時間でも）coNPのアルゴリズムでさえ解けない。
➢特に、O’Donnellの予想の下でMKTP ∉ coNP.

目次
1. 回路最小化問題（MCSP）について
2. 平均計算量とは
3. 自然な証明について
4. MCSPの最悪計算量から平均計算量への帰着について（疑似ランダム自己帰着性）

回路下界技法の発展 (1980s)
𝐏 ≠ 𝐍𝐏 に対するアプローチ
定数段かつ多項式として回路の表現力の限界サイズの回路を調べる技法が発展してきた。

P ⊈ AC0P ⊈ AC0 [𝑝][Ajtai83, FSS84, Yao85, Hastad89][Razborov87, Smolensky87]（AC 0 回路の例）

未解決:

NP ⊈ TC∧

0NP ⊈ P/poly¬∨𝑥1𝑥2𝑥3

回路下界技法の発展 (1980s)
𝐏 ≠ 𝐍𝐏 に対するアプローチ
として回路の表現力の限界を調べる技法が発展してきた。

P ⊈ AC0P ⊈ AC0 [𝑝]

未解決:NP ⊈ TC[Ajtai83, FSS84, Yao85, Hastad89][Razborov87, Smolensky87]
多項式サイズの回路（AC 0 回路の例）∧0NP ⊈ P/poly¬∨𝑥1𝑥2𝑥3

回路下界技法の発展 (1980s)
𝐏 ≠ 𝐍𝐏 に対するアプローチ
閾値ゲートからなる定数段の回路として回路の表現力の限界を調べる技法が発展してきた。

P ⊈ AC0P ⊈ AC0 [𝑝][Ajtai83, FSS84, Yao85, Hastad89][Razborov87, Smolensky87]（TC 0 回路の例）

未解決:

NP ⊈ TC

MAJ0NP ⊈ P/poly¬

MAJ𝑥1𝑥2𝑥3

自然な証明[Razborov & Rudich 1997]➢ P vs NP問題の難しさを示す
一つのバリア

自然な証明が存在する
自然な証明が存在しない

P ⊈ AC0
P ⊈ AC0 [𝑝]NP ⊈ TC0
NP ⊈ P/poly(未解決)自然な証明: MCSPの部分問題➢ AC0 回路に対する自然な証明とは多項式時間アルゴリズムであって、1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さいAC0 回路で実現できるときは“NO”と答える
𝑥1 ∧ 𝑥2 ∧ 𝑥3∧
𝑥1 𝑥2 𝑥3𝒙𝟏𝒙𝟐𝒙𝟑

𝒇 𝒙 𝟏 , 𝒙𝟐 , 𝒙𝟑00000010010001101000101011001111“NO”（サイズ1のAC 0 回路で実現できる）

自然な証明: MCSPの部分問題➢ AC0 回路に対する自然な証明とは多項式時間アルゴリズムであって、1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さいAC0 回路で実現できるときは“NO”と答える

𝒙𝟏𝒙𝟐𝒙𝟑𝒇 𝒙 𝟏 , 𝒙𝟐 , 𝒙𝟑00010011010001111000101011011110“YES”

0AC に対する自然な証明➢ AC0 回路に対する自然な証明は存在するか？
➢ 回路下界の証明をアルゴリズム的に見直すと、存在することがわかる！

P ⊈ AC0[Ajtai83, FSS84, Yao85, Hastad89]➢ 実はほとんど全ての回路下界の証明は自然な証明になっている。

自然な証明の存在について
自然な証明が存在する

自然な証明が存在しない

P ⊈ AC0
P ⊈ AC0 [𝑝]NP ⊈ TC0

NP ⊈ P/poly(解決済み)(未解決)

定理 [Razborov & Rudich (1997)]（一方向性関数が存在するならば、）𝐏/𝐩𝐨𝐥𝐲に対する自然な証明は存在しない。

「回路最小化問題のゼロ誤りアルゴリズム」＝「自然な証明」（SIZE(𝑠)に対する）

自然な証明

主張

⟺

1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さい回路で実現できるときは“NO”と答える

MCSP 𝑠 を解く
ゼロ誤りアルゴリズム

YES

NOインスタンス「回路最小化問題のゼロ誤りアルゴリズム」＝「自然な証明」（SIZE(𝑠)に対する）

自然な証明

⟹

1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さい回路で実現できるときは“NO”と答える

MCSP 𝑠 を解く
ゼロ誤りアルゴリズム

YES
“NO”
“YES”

自然な証明
NOインスタンス「回路最小化問題のゼロ誤りアルゴリズム」＝「自然な証明」（SIZE(𝑠)に対する）

自然な証明

⟹

1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さい回路で実現できるときは“NO”と答える

ゼロ誤りアルゴリズム

MCSP 𝑠 を解く
ゼロ誤りアルゴリズム

YES
“?”
“0”
NOインスタンス「回路最小化問題のゼロ誤りアルゴリズム」＝「自然な証明」（SIZE(𝑠)に対する）

自然な証明

⟸

1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さい回路で実現できるときは“NO”と答える

ゼロ誤りアルゴリズム

MCSP 𝑠 を解く
ゼロ誤りアルゴリズム

“1”
YES
“?”
“0”
NOインスタンス「回路最小化問題のゼロ誤りアルゴリズム」＝「自然な証明」（SIZE(𝑠)に対する）

自然な証明

⟸

1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さい回路で実現できるときは“NO”と答える

MCSP 𝑠 を解く
ゼロ誤りアルゴリズム

“NO”
YES
“NO”
“YES”

自然な証明
YESインスタンスの数 = 𝑠 𝑂 𝑠𝑛2≪ 全体のインスタンスの数 = 2

NOインスタンス「回路最小化問題のゼロ誤りアルゴリズム」＝「自然な証明」（SIZE(𝑠)に対する）

自然な証明

⟺

1. 多くの真理値表について“YES”と答えるが、2. 真理値表が小さい回路で実現できるときは“NO”と答える

MCSP 𝑠 を解く
ゼロ誤りアルゴリズム

YESNOインスタンス

目次
1. 回路最小化問題（MCSP）について
2. 平均計算量とは
3. 自然な証明について
4. MCSPの最悪計算量から平均計算量への帰着について（疑似ランダム自己帰着性）

ランダム自己帰着 (Random self-reduction)
問題𝐿が（1回のクエリの）ランダム自己帰着できる
def⟺ ∃ 乱択多項式時間機械
入力: 𝑥 ∈ 0,1 𝑁（ランダムな）

クエリ𝑞

問題𝐿のオラクル

回答𝐿(𝑞)••

は問題の答え𝐿 𝑥 を高い確率で答える。
𝑞は 0,1 𝑁 上で一様に分布する。

最悪計算量から平均計算量への帰着• 問題𝐿がランダム自己帰着できる• あるアルゴリズム が𝐿を平均的に解く⟹ 𝐿を全ての入力で解くアルゴリズムが存在する。
入力: 𝑥 ∈ 0,1 𝑁

平均的に解くアルゴリズムで置き換える
𝑁

クエリ𝑞 ∼ 0,1
回答𝐿(𝑞)

答え𝐿 𝑥 を出力

オラクル𝐿

NP完全問題のランダム自己帰着性定理 ([Feigenbaum & Fortnow 1993], [Bogdanov & Trevisan 2006])（多項式階層がつぶれない限り）
NP完全問題はランダム自己帰着を持たない。

➢ もしもMCSPがランダム自己帰着性をもつならば、MCSPがNP完全でないことの強い証拠を与える。

疑似ランダム自己帰着(Pseudorandom self-reduction)

問題𝐿が疑似ランダム自己帰着できる
def⟺ ∃ 乱択多項式時間機械
入力: 𝑥 ∈ 0,1 𝑁（ランダムな）

クエリ𝑞

問題𝐿のオラクル

回答𝐿(𝑞)••

は問題の答え𝐿 𝑥 を高い確率で答える。
𝑞と 0,1 𝑁 上の一様分布は多項式時間で識別不可能。

我々の成果：回路最小化問題の疑似ランダム自己帰着性定理

一方向性関数が存在するならば、（約束付きの）回路最小化問題は疑似ランダム自己帰着性をもつ。
➢ 証明のアイディア：疑似乱数関数生成器とXORをとる

未解決問題

妥当な仮定の下でNP完全問題は疑似ランダム自己帰着性をもつか？

まとめ• 疑似ランダム自己帰着性という、最悪計算量から平均計算量への弱い帰着の概念を導入• （一方向性関数の存在の下で）MCSPはその性質を持つ。
• MKTP（MCSPの時間制限付きコルモゴロフ記述量版）
はRandom 3SAT困難。特に、MKTP ∉ coNPを示す初めての証拠を与えた。