Identifying an Honest
NPEXP Oracle Among Many(CCC’15)
平原 秀一
東京大学 修士課程2年
ERATOリサーチアシスタント

ERATO感謝祭 Season II 2015年8月4日

概要

Dishonest oracleHonest oracle

Which is honest?
Selector (選択者)

貢献ポイント

1. 選択者という概念を定式化した。
 選択者の存在 ⟺ 短いアドバイスの消去
2. EXPNP 完全問題に対する選択者の存在を示した。

背景: Instance checker [Blum & Kannan (1989)]
問題𝐿に対するInstance checkerとは、多項式時間の乱択機械であって、与えられたプログラムが与えられたインスタンス𝜑で正しく𝐿(𝜑)を計算しているかを(低い誤り確率を許して) 判定するもの。
Instance checker for SAT

Given: input 𝜑

Is the program buggy
or correct on 𝜑?

Queries:Is 𝜓 satisfiable?

I cansolve SAT!!

Answers
Possibly buggy program(modeled by black-box access to an oracle)Instance checkerの存在について
指数時間完全問題に対してInstance checkerが存在[Babai, Fortnow & Lund (1991)]

EXP完全

EXP
NP

coNP

P

Instance checkerの存在について
指数時間完全問題に対してInstance checkerが存在[Babai, Fortnow & Lund (1991)]

EXP完全

EXP
Instance checkerは
NEXP ∩ coNEXPにのみ存在

NP

coNP

P

(Probabilistic) Selector for SAT
Given:
1. An input 𝜑, and
2. access to two oracles
one of which is honest.

Task:
compute SAT 𝜑
with the help of the oracles

Given: input 𝜑Selector for SATIs 𝜑satisfiable?

(Probabilistic) Selector for SAT
𝜓 is notsatisfiable!

𝜓 issatisfiable!

Given:
1. An input 𝜑, and
2. access to two oracles
one of which is honest.

Task:
Queries:Is 𝜓 satisfiable?

Given: input 𝜑Selector for SAT

compute SAT 𝜑
with the help of the oracles

Is 𝜑satisfiable?

(Probabilistic) Selector for SAT
𝜓 is notsatisfiable!

𝜓 issatisfiable!

Dishonest oracle

Honest oracle

Given:
1. An input 𝜑, and
2. access to two oracles
one of which is honest.

Task:
compute SAT 𝜑
with the help of the oracles

Queries:Is 𝜓 satisfiable?
Arbitraryanswers

Correct answers

Given: input 𝜑Selector for SAT

Is 𝜑satisfiable?

Why is it called “selector”?
YES

YES

Dishonest oracle

Honest oracle

Given:
1. An input 𝜑, and
2. access to two oracles
one of which is honest.

Task:

Is 𝜑 satisfiable?
Arbitraryanswers

Correct answers

Given: input 𝜑Selector for SAT

compute SAT 𝜑
with the help of the oracles

Why is it called “selector”?
YES

YES

Dishonest oracle

Honest oracle

Given:
1. An input 𝜑, and
2. access to two oracles
one of which is honest.

Task:
compute SAT 𝜑
with the help of the oracles

Is 𝜑 satisfiable?
Arbitraryanswers

Correct answers

Given: input 𝜑Selector for SAT

The answer
must be YES!!

Why is it called “selector”?
YES
Dishonest oracle

Honest oracleNO

1. An input 𝜑, and
2. access to two oracles
one of which is honest.

Essential Task:
determine which is honest
when they disagree on 𝜑.

Is 𝜑 satisfiable?
Arbitraryanswers

Given:

Correct answers

Given: input 𝜑Selector for SAT

Which ishonest?

選択者の定義
定義 (選択者)
問題𝐿に対する選択者𝑆とは、多項式時間乱択チューリン
グマシンであって、以下の条件を満たすものをいう。
𝐴0 = 𝐿 or 𝐴1 = 𝐿 ⟹ Pr 𝑆 𝐴0 ,𝐴1 𝑥 = 𝐿 𝑥 ≥ 0.99

(for any 𝐴0 , 𝐴1 ⊆ 0,1 ∗ , 𝑥 ∈ 0,1 ∗ )Oracle 𝐴1

Oracle 𝐴0

Queries:𝐿 𝑞 =?
Arbitraryanswers

Correct answers (YES/NO)

Selector 𝑆 for a language 𝐿(polynomial-time probabilistic oracle TM)

Instance Checker vs. Selectorが存在すれば、Instance checker
ひとつのオラクルを見て正直かどうか判定するも存在する。

Selector
二つのオラクルのうち正直な方を選択する

例: PNP完全問題に対する選択者

定義 （𝐏 𝐍𝐏 完全問題: 辞書順最大の充足割当て）

入力: 充足可能な𝑛変数論理式 𝜑 と 自然数 𝑘 ∈ 1, … , 𝑛
出力: 𝜑の辞書順最大の充足割当ての𝑘番目の変数の割り当てが真かどうか。
主張: この問題に対して選択者を構成できる。
 入力 𝜑, 𝑘 と二つのオラクルが与えられる。

Step 1. それぞれのオラクルの主張する割当てを得る。

辞書順最大の充足割当ては...

𝑎0𝑎1

例: P

NP

完全問題に対する選択者

定義 （𝐏 𝐍𝐏 完全問題: 辞書順最大の充足割当て）

入力: 充足可能な𝑛変数論理式 𝜑 と 自然数 𝑘 ∈ 1, … , 𝑛
出力: 𝜑の辞書順最大の充足割当ての𝑘番目の変数の割り当てが真かどうか。

𝑥1 = 1𝑥1 = 0

質問: 𝜑, 1（充足解の1番目の変数への割り当ては何？）

例: P

NP

完全問題に対する選択者

定義 （𝐏 𝐍𝐏 完全問題: 辞書順最大の充足割当て）

入力: 充足可能な𝑛変数論理式 𝜑 と 自然数 𝑘 ∈ 1, … , 𝑛
出力: 𝜑の辞書順最大の充足割当ての𝑘番目の変数の割り当てが真かどうか。

𝑥1 = 1𝑥1 = 0𝑥2 = 1𝑥2 = 1
質問: 𝜑, 2（充足解の2番目の変数への割り当ては何？）例: P

NP完全問題に対する選択者

定義 （𝐏 𝐍𝐏 完全問題: 辞書順最大の充足割当て）

入力: 充足可能な𝑛変数論理式 𝜑 と 自然数 𝑘 ∈ 1, … , 𝑛
出力: 𝜑の辞書順最大の充足割当ての𝑘番目の変数の割り当てが真かどうか。

𝑥1 = 0𝑥2 = 1𝑥2 = 1...

...

𝑎0 = 11 … 0

𝑥1 = 1𝑥𝑛 = 0𝑥𝑛 = 1𝑎1 = 01 … 1

例: P

NP

完全問題に対する選択者

定義 （𝐏 𝐍𝐏 完全問題: 辞書順最大の充足割当て）

入力: 充足可能な𝑛変数論理式 𝜑 と 自然数 𝑘 ∈ 1, … , 𝑛
出力: 𝜑の辞書順最大の充足割当ての𝑘番目の変数の割り当てが真かどうか。
 Step 1. それぞれのオラクルの主張する割当てを得る。

𝑎0 = 11 … 0

𝑎1 = 01 … 1

 Step 2. 大きい方の割当てが充足解か調べる。

:

𝑎0 > 𝑎1 なので𝜑 𝑎0 を評価する。

𝑎0 が充足解であれば（𝜑 𝑎0 = true）、そうでなければを信じる。

を信じる。
（構成終わり）

Instance Checker vs. Selector

Instance checker
ひとつのオラクルを見て正直かどうか判定する

Selector
二つのオラクルのうち正直な方を選択する

Instance Checker vs. Selector

Instance checker

Selector

二つのオラクルのうちひとつのオラクルを見て 反例:
正直かどうか判定する
EXPNP 完全問題 正直な方を選択する（NEXP = EXP NP でない限り）

Instance Checker vs. Selector
主定理
EXPNP 完全問題に対する選択者が存在する。

Instance checker

Selector

二つのオラクルのうちひとつのオラクルを見て 反例:
正直かどうか判定する
EXPNP 完全問題 正直な方を選択する（NEXP = EXP NP でない限り）

P

NPとは

例:辞書順最大の充足割当て

NP
P

NP coNPP

主結果: 完全問題について∃選択者

NP
EXP とは
例:指数サイズの論理式に対する辞書順最大の充足割当て

EXP

NP

EXP
P NP
NP

coNP

P

主結果: 完全問題について∃選択者

NP
EXP とは
例:指数サイズの論理式に対する辞書順最大の充足割当て

EXP

NP

EXP
Instance checkerの存在範囲（EXP NP = NEXPでない限り、）
EXP NP 完全問題に対してinstance checkerは存在しない。

P NP
NP

coNP

PここまでInstance checker「オラクルが正直か確認する」ことより「正直なオラクルを選ぶ」方が真に簡単。
selector

ここから選択者が「短いアドバイスの消去」という条件を特徴付けることについて。

アドバイスとは
入力の長さ𝑛のみに依存する、計算を補助するデータ𝛼𝑛 ∈ 0, 1 ∗ のこと。
定義 (対数長のアドバイスで解ける問題全体)
問題𝐿に対し、 𝐿 ∈ 𝐏/𝐥𝐨𝐠 とは、1. 各𝑛について 長さ𝑂 log 𝑛 のアドバイス𝛼𝑛 が存在し、2. 多項式時間チューリングマシン𝑀 が存在して、長さ𝑛の任意の入力𝑥に対し 𝑀 𝑥, 𝛼𝑛 = 𝐿(𝑥) となること。
アドバイス𝛼𝑛(前計算されたもの)∀入力𝑥 ∈ 0,1 𝑛
機械 𝑀

出力: 𝐿(𝑥)（アドバイスは入力𝑥には依存せず、入力の長さ𝑛にのみ依存する。）

動機: 短いアドバイスの消去[Karp & Lipton (1980)]

SAT ∈ 𝐏/𝐥𝐨𝐠 ⟹ SAT ∈ 𝐏

 SATを解くためには対数長のアドバイスは不要[Trevisan & Vadhan (2002)]

EXP ⊆ 𝐁𝐏𝐏/𝐥𝐨𝐠 ⟹ EXP ⊆ 𝐁𝐏𝐏

 EXP完全問題に対するinstance checkerが存在することから従う。

Q.

一般に, アドバイスを消去できる条件は？
答え: 選択者が存在すること（必要十分条件）∃選択者⟹ 1bitのアドバイスの消去

1. 問題 𝐿 が1bitのアドバイスで計算できるとする。

i.e. ある機械𝑀が存在し、アドバイス”0”
か”1”を与えると問題𝐿を正しく計算する。
2. 二つのオラクルを以下のように定める:

defdef==Advice “0”Query 𝑞𝑀 𝑞, 0

Advice “1”𝑀 𝑞, 1

どちらか一方は正直なオラクルになる！
⟹ 選択者は(アドバイスなしで)𝐿を正しく計算する。

Key Lemma: “Among Many”
Identifying an honest oracle
among polynomially many

Identifying an honest oracle among two(Honest)(Honest)=On input 𝑥,outputs 𝐿(𝑥) Able to remove advice of 1 bit

On input 𝑥,outputs 𝐿(𝑥) Able to remove advice of 𝑂 log 𝑛 bits

Proof of the Key Lemma (1/2)• We have a selector
that identifies an honest(Honest)oracle among two.
• Given input 𝑥 and many oracles
011• Ask them about 𝑥:
𝐿 𝑥 is 0• Divide them into two teams:

Idea: “Tournament”

We claim
𝐿 𝑥 = 0.

Which teamshould we trust?

We claim
𝐿 𝑥 = 1.
(Honest)Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

(Honest)Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

0(Honest)

Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

0(Honest)

I doubt!!

Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

(Honest)Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

1(Honest)

Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

1(Honest)

I doubt!!

Proof of the Key Lemma (2/2)

We claim𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

(Honest)Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

1(Honest)

Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

1(Honest)

I doubt!!

Proof of the Key Lemma (2/2)

We claim
𝐿 𝑥 = 1.

We claim
𝐿 𝑥 = 0.

(Honest)

I trust,so the answer is 1!
The honest oracle always wins!

Removing advice of size 𝑂 log 𝑛
Advice “0”Advice “1”𝑀 𝑞, 1
𝑀 𝑞, 0𝑞𝑞

Removing advice of size 𝑂 log 𝑛
Advice “00”Advice “01”𝑀 𝑞, 01
𝑀 𝑞, 00

𝑞

Advice “10”Advice “11”𝑀 𝑞, 10𝑞 𝑞

𝑀 𝑞, 11𝑞
 Able to remove advice of 2 bits

Corollary (Selector ⇒ Removing short advice)
Suppose that there exists a selector for a paddable language 𝐿.
Then, 𝐿 ∈ 𝐁𝐏𝐏/𝐥𝐨𝐠 implies 𝐿 ∈ 𝐁𝐏𝐏.

まとめ
選択者という概念を導入した。
二つのオラクルのうちから正直なオラクルを選ぶ。
多項式個のオラクルのうちから正直なオラクルを選ぶ、といっても同じ。

Instance checkerの仕事よりも選択者の仕事の方が真に簡単。（EXPNP 完全問題）
短いアドバイスの消去について、今まではinstancecheckerが使われてきたが、実は選択者が必要十分条件を与える。