1. No category

計算量演習
第七回
平成 27 年 1 月 2 日
或る問題 B を解くとわかっている算法を，その中身を気にせずに，別の計算手順の一
部として利用することがある．計算量理論においても「仮に問題 B が解けるとして」話
を進めると議論の助けになることがある．B の解決に係る困難はさて措き，それに加えて
如何なる困難があるか，相対的に調べるのである．このために，動作中に B の答を必要
に応じて尋ねる仕組をもつ神託機械を用いる．
神託機械とチューリング帰着
神託チューリング機械（以下単に神託機械と呼ぶ）とは，これまでのチューリング機械
の機能に加え，計算中に神託と呼ばれる判定問題 B に質問をすることができるものであ
る．このために「質問テープ」「回答テープ」があり，特別な状態として q質問前 と q質問後
とをもつ．状態が q質問前 になると，その時に質問テープに書かれている
字列 x に対し，
次の時刻には，状態が q質問後 になるとともに，回答テープに B(x) が書込まれる*1 ．つま
り B を解くに要する時間や空間は考えず，質問すれば直ちに答が外から与えられるとす
るのである．神託機械 M に神託 B を与えたものを M B で表す．
この M B が問題 A を解 くとき，M を A から B へのチューリング帰着（Turing
reduction）とも呼ぶ．特に M が多項式時間限定に取れるとき，A は B へ多項式時間
チューリング帰着（クック帰着）するという．
このように「B を
うと A が解ける」という概念としては第三回や第五回で扱った多
対一帰着もあるが，多対一帰着ではその「 い方」が，A の個例 x を B の個例 T (x) に変
換するという形に限られており，答 B(T (x)) には手を加えずそのまま A の答とした（図
3.1）．チューリング帰着はその制限を去って計算中いつでも B の助けを求められるよう
にしたものであり（図 7.1），また A が判定問題でない場合にも考えることができる．例
えば問 2.5 では，もし判定問題 sat が P に属せば探索問題 findSat が FP に属すること
を示すため，findSat から sat への多項式時間チューリング帰着を作ったのであった．
*1
B が約束つき問題（→第二回）である場合，dom B に属しない質問 x に対しては毎回出鱈目の答が返さ
れるとし，神託機械はその結果によらず正しく振舞わねばならないとする．
7-1
B
M
A
x
A(x)
図 7.1 図 3.1 の多対一帰着とは異なり，チューリング帰着においては，神託機械 M が B に多く
の質問をし，その結果を
C
問 7.1
1
って問題 A に答えることができる．
coNP の任意の問題は sat へ多項式時間チューリング帰着することを示せ．
何故これまではこの強力なチューリング帰着ではなく多対一帰着を
ったかといえば，
単に「多対一帰着でも事足りたから」に過ぎない．例えば「多項式時間で sat が解ければ
どの問題 A ∈ NP も解ける」と言いたいだけなら，多項式時間で A を sat にチューリン
グ帰着すれば十
だが，実際には多対一帰着もできるので折角だからその形で NP 完
性
を述べたまでである．また NP は多対一帰着については閉じている（→問 5.1（1））ので，
NP 完 性の定義にはそれを った方が若干気 が良いというのもある．
相対化
上では神託機械 M に神託 B を与えた M B が別の問題 A を解くことを考えたが，「解
く」の代りに第四回の「R 決定」「N 決定」などを考えることもできる．すなわち級 P，
FP，NP，RP，BPP の定義に現れた機械 M の代りに，神託機械に問題 B を神託として与
えた M B を
って得られる級を，それぞれ PB ，FPB ，NPB ，RPB ，BPPB で表す．
問題 A が B に多項式時間チューリング帰着するとは，この記法で書けば A ∈ FPB な
いし A ∈ PB ということになる．また例えば A ∈ NPB とは，或る多項式時間限定の神託
機械 M が存在して M B が A を N 決定することを意味する．
7-2
これまでの計算量級に関する議論の多くは，機械に任意の神託 B を附けてもそのまま成
立つ．このように「神託 B つきで同じ議論を行う」ことを B による相対化
（relativization）
と呼ぶ．例えば図 4.1 の包含関係は各級に神託 B を与えても
し，sat が NP 完
く同じ議論により成立つ
ということも次のごとく相対化する．
回路やその一種である論理式においても，機械に神託 B を与えたのと同様に，B を表
す素子を
った計算を考えることができる．すなわち各 l ∈ N に対して l 入力 1 出力の素
子 Bl があり，これを回路の中で自由に ってよい．回路を命令列とする考え方でいえば，
xi = B(xj1 , . . . , xjl ) の形の命令（l ∈ N は任意，j1 ，…，jl は i 未満の正整数）も許すとい
うことである．このように B を
を判定する問題を circSat
B
った回路や論理式が与えられたとき，その充足可能性
や satB と書くことにする．
これらの問題 circSatB ，satB は，B を神託として与えられれば容易に N 決定でき，
したがって NPB に属する．また circSat や sat が NP 完
であるという議論も相対化
B
する．すなわち circSatB や satB は多項式時間多対一帰着 ≤FP
m の下で NP 完
でも
ある（これは B の現れる回路や論理式が多対一帰着により作られるのであり，多対一帰着
そのものの計算に神託 B を用いるのではない）．
C
問 7.2
13＋1
（約束なし）判定問題 B ∈ NP ∩ coNP について
（1）satB ∈ NP を示し，これにより NPB = NP を示せ．
（2）PB ⊆ NP ∩ coNP を示せ．
C
問 7.3
5＋3
（1）次の約束つき判定問題 xSat について sat ∈ PxSat を示せ．
xSat の個例は二つの命題論理式の組 (ϕ, ψ) であって丁度片方のみが充足可能で
あることが約束されている．これに対し，充足可能なのが ϕ であるか判定する．
（2）NP ̸= coNP とする．問 7.2（2）の主張は，B を約束つき判定問題にしてしまうと
成立たないことを示せ．
C
問 7.4
2＋4＋4
以上では神託 B を判定問題に限ったが，より一般に探索問題のうち多項式均衡な
もの（つまり或る多項式 p が存在し任意の個例 x に対して B[x] の元はみな長さが p(|x|)
以下であるもの）に拡げてもよい．すなわち B への質問 x に対しては B[x] の元が一つ返
され，機械はいずれの答が選ばれるかによらず正しく振舞わねばならぬものとする*2 ．
*2
B を多項式均衡な問題に限ったのは，そうでない場合に同じ定義をそのまま採用してしまうと，神託が返
す答を読む時間すらない虞があり，良い定義といえなくなるからである．本問の findSat や factor は
多項式均衡なので，神託機械の時間制限を十
大きな多項式にしておけばその心配はない．
7-3
さて sat は（多項式時間チューリング帰着に関しても勿論）NP 完 であり，NP は Psat
や PfindSat に含まれる（また一致する）．このことを以て findSat を（それ自身が判定問
題ではないので「NP 完
」とはいわれないが）「NP 困難」と言うことがある．
一方，与えられた正整数を素因数 解する問題 factor（→第二回）は，FP に属するか
不明だが，次の理由から，NP 困難というわけでもなさそうだと考えられている．
（1）与えられた正整数の組 (n, b) に対し，n に b 未満の素因数があるか判定する問題を
factorBelow とする．factor ∈ FPfactorBelow を示せ．
（2）factorBelow ∈ NP ∩ coNP を示せ．問 4.7 の結果 primes ∈ NP を用いよ．
（3）NP ̸= coNP とする．NP ⊆ Pfactor でないことを示せ．問 7.2 を用いよ．
次の問 7.5，7.6 で見るように，PB = NPB という主張は B によって成否が変る．故に
P ̸= NP 予想は，「任意の神託で相対化できるような議論」によっては解決し得ない．
B
問 7.5
B を PSPACE 完 問題（例えば qbf）とする．PB = NPB を示せ．
C
問 7.6
PB ̸= NPB となる判定問題 B の存在を示そう．
1＋6＋4＋4
（1）任意の判定問題 B に対し，次の判定問題 UB が NPB に属することを示せ．
UB (x) =
!
1 或る y ∈ {0, 1}|x| について B(y) = 1 のとき
0 すべての y ∈ {0, 1}|x| について B(y) = 0 のとき
（2）（決定性）多項式時間神託機械 M を一つ取る．判定問題 B であって M B が UB を
解かない（すなわち UB の或る個例 x について出力が UB (x) と異なる）ようなも
のを一つ作れ．
（3）（2）よりも少し強いことを示そう．約束つき判定問題 C（→第二回）が有限である
とは約束 dom C が有限であることをいう．また約束つき判定問題 B が C を含む
とは，任意の x ∈ dom C について x ∈ dom B かつ B(x) = C(x) なることをいう．
任意の有限な約束つき判定問題 C と任意の多項式時間神託機械 M とに対して，C
を含む有限な約束つき判定問題 B が存在し，M B が UB を解かないことを示せ．
（4）多項式時間神託機械をすべて枚挙して M1 ，M2 ，
…とし，これらについて順に
（3）
を
繰返し用いることで，UB ∈
/ PB なる判定問題 B を作れ．
7-4
多項式時間階層
以下では問題の集合 C について PC =
C
"
PB のように書く（NPC ，RPC なども同様）．
B∈C
NP
p
p
Σpk
Σ0 = P とし各 k ∈ N で Σk+1 = NP とする．例えば Σp3 = NPNP ．列 Σp0 ⊆ Σp1 ⊆
" p
Σp2 ⊆ . . . を多項式時間階層（polynomial-time hierarchy）と呼ぶ．PH =
Σk とする．
k∈N
問 7.7
10＋3
任意の k ∈ N について，
（1）判定問題 A が Σk+1 に属するには，多項式 p と（約束なし）判定問題 R ∈ Σk とが
p
p
存在し，A の任意の入力 u について次が成立つことが必要十
であることを示せ．
A(u) = 1 ⇐⇒ ∃v ∈ Σ p(|u|) . R(u, v) = 0
（2）判定問題 A が Σk に属するには，多項式 p と（約束なし）判定問題 R ∈ P とが存在
p
し，A の任意の入力 u について次が成立つことが必要十
であることを示せ．
A(u) = 1 ⇐⇒ ∃v1 ∈ Σ p(|u|) . ∀v2 ∈ Σ p(|u|) . ∃v3 ∈ Σ p(|u|) . . . Qvk ∈ Σ p(|u|) .
R(u, v1 , . . . , vk ) = 1
但し Q は k が奇数なら ∃，偶数なら ∀．
B
（1）のヒント A ∈ Σk+1 ならば，或る B ∈ Σk が存在して A ≤FP
m sat ．
p
p
この（2）の条件は多項式空間限定の機械で確かめられる（→問 3.5 と同様）から，（直接
にも示せるが）PH ⊆ PSPACE が成立つ．
多項式時間階層は P = Σ0 ! Σ1 ! Σ2 ! . . . のごとく各層みな相異なるというのが大方
p
p
p
の予想である．もしこれに反して或る層 k ∈ N で Σk = Σk+1 ならば，定義より明らかに
p
p
以降の層もみな等しく Σk = PH となる．これを多項式時間階層が「潰れる」という．も
p
し P = NP なら勿論すべて潰れるが，そうでなく或る層より上のみ潰れる可能性もある．
C
問 7.8
もし PH = PSPACE ならば多項式時間階層が潰れることを示せ．
ヒント
PSPACE 完 問題をとる．PH = PSPACE ならばそれは或る Σpk に属する．
7
7-5
C
問 7.9
C
問 7.10
BPPBPP = BPP を示せ*3 ．
11
10＋6＋2
（1） 字列 x，y ∈ {0, 1}k のビット毎の排他論理和を x ⊕ y ∈ {0, 1}k で表し，
集合 X ，Y ⊆ {0, 1}k に対しては X ⊕ Y = { x ⊕ y : x ∈ X, y ∈ Y } とする．
多項式 p，q を適当に定めると，任意の k ∈ N と集合 Y ⊆ {0, 1}k とについて
次が成立つことを示せ．組 s = (s1 , . . . , sp(k) ) ∈ ({0, 1}k )p(k) に対して f (Y, s) =
|Y ⊕ {s1 , . . . , sp(k) }|/2k と書くことにすると，
• |Y |/2k ≥ 1 − 1/q(k) ならば，過半数の s ∈ ({0, 1}k )p(k) について f (Y, s) = 1
• |Y |/2k ≤ 1/q(k) ならば，すべての s ∈ ({0, 1}k )p(k) について f (Y, s) < 1/2
!
# は多項式時間限定の機械で R 決定さ
（2）（1）を用いて RPRP = BPP を示せ．但し RP
れる約束つき問題の級である（→第二回，第四回）．
（3）（2）を用いて BPP ⊆ Σ2 を示せ．
p
締切（事務室印有効）
B
1 月 13 日（火）
C
1 月 23 日（金）
*3
問 5.6 のヒントのように BPP の誤り確率を著しく減らすことができることを用いてよい．
7-6