計算量演習
第五回
平成 26 年 12 月 5 日
前回までに，様々な計算資源の制限下で処理「できる」問題を集めた級を定義した．で
は逆に問題が処理し難く複雑であると主張するにはどうすればよいか．そのために帰着の
概念が役立つ．問題 A が問題 B に帰着するとは，B が解ければこれを
るという相対的な難しさの比
って A も解け
であった．多くの難しそうな問題 A が B に帰着するなら
ば B は恐らく難しかろう．この考えに立って各計算量級の中でも最も難しいといえる問
題を完
問題という．NP，PSPACE など主な級については，今回見るように多くの完
問題が知られている．
前回に引続き今回も主に判定問題のみを扱う．
NP 完 問題
或る問題を解くのが困難であると主張するには，本来ならばその問題が何らかの級に属
しないことを証明できればよいのだが，既に述べたように，P や NP のごとく互に異なる
と予想される計算量級も，本当に異なるとは示されていない．つまり P に属していなそう
な NP 問題であっても，そのことを証明できないのである．
そこで帰着の概念が役立つ．判定問題 A から B への多対一帰着とは，A の任意の
個例を，答が同じ B の個例に変換する函数，すなわち A の任意の個例 x について
A(x) = B(T (x)) を満すような函数 T であった（→第三回）．この変換が多項式時間でで
きる（A ≤FP
m B ）とき，B は少くとも A 以上に困難であると言ってよかろう．この関係は
FP
FP
推移的，すなわち A ≤FP
m B ≤m C ならば A ≤m C が成立つ．これを用いて NP に属す
る問題どうしを比べたとき，最も困難であるというのが次に定義する NP 完
5-1
性である．
NP 完 性
問題 B ∈ NP が NP 完 （NP-complete）
であるとは，任意の A ∈ NP に対して A ≤FP
m B
が成立つことをいう．
B
問 5.1
（1）A ≤FP
m B かつ B ∈ NP ならば A ∈ NP が成立つことを示せ．
（2）A ≤FP
m B ∈ NP かつ A が NP 完
（3）もし或る NP 完
つまり NP 完
ならば B もまた NP 完
であることを示せ．
問題が P に属すれば，NP = P であることを示せ．
な問題は或る意味で NP のすべての問題の難しさを代表するといえる．
NP 完 問題は存在する．例えば問 2.7 の問題 timeSim の「N 決定」版として次の判
定問題 timeNSim を考えると，これは NP 完
である．
入力
乱択機械 M と
出力
M に x を入力して時間 t だけ動かすと，受理する 岐があるか．
字列 x と羅列表記された数 t ∈ N との組 (M, x, 0t )．
何となれば，勝手な A ∈ NP を考える．多項式 p と，A を N 決定する p 時間限定の乱択
機械 M とが存在する．すると A の各個例 x に対して A(x) = timeNSim(M, x, 0p(|x|) )．
つまり x を (M, x, 0p(|x|) ) に移す函数が A から timeNSim への多対一帰着になってお
り，この函数は明らかに多項式時間で計算できるから，A ≤FP
m timeNSim．この A は任
意であったから timeNSim は NP 完
様々な NP 完
である．
問題
timeNSim はやや人工的だが，様々な 野の自然な問題にも NP 完 なものが数多く
ある．問 5.1（2）に言う通り，或る問題 A が NP 完
ならば，A ≤FP
m B なる別の問題
B ∈ NP も NP 完 とわかる．以下この方法で多くの問題の NP 完 性を示そう．
まず与えられた回路が充足可能か判定する問題 circSat（→問 3.7）は NP 完 である．
次のごとく timeNSim ≤FP
m circSat が成立つからである．
5-2
x
r
...
init
x
d
b
..
.
d0
5.1.1
字列 x と時点表示 d とビット b ∈
{0, 1} を与えると次の時点表示 d′ を答える
回路．図 2.2 は決定的機械に関する同様の
isAcc
9
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
=
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
;
t
回路であったが，今度は乱択機械であるた
め乱択 b に依存して d′ が決る．
1/0
5.1.2 図 5.1.1 の回路を組合せて得られる回路．
字列 x と乱数列 r とから受理・非受理を計算す
る．
図 5.1 乱択機械の動きを模倣する回路．
これは問 2.7 と殆ど同じ議論によりわかる．問 2.7 は makeNextID の算法を用い
て timeSim ≤FP
m cEval という帰着を作ることにより timeSim ∈ P を示したと見る
ことができる．同様のことを乱択機械について行おう（図 5.1）．乱択機械の動きは各時
点で二通りに
岐するから，一遷移を表す回路 makeNStep(M, 0n , 0s ) は図 2.2 の代
りに図 5.1.1 のごとくビット b にも依存して次の遷移を決めるものとなる．この回路を
t 個組合せて得られる図 5.1.2 の回路 makeNCirc(M, 0n , 0s , 0t ) は，機械 M への入力
字列 x と乱数列 r とを受取り，この機械が遷移 t 回後までに受理するか否かを求め
る回路である．この回路をそれぞれ構成する問題 makeNStep，makeNCirc は問 2.7
のときと同様に容易である（FP に属する）．timeNSim の個例 (M, x, 0t ) に対し，回路
makeNCirc(M, 0|x| , 0t , 0t ) に x を代入したもの（つまり後は r のみを入力すれば値が決
るような回路）を T (M, x, 0t ) とする．この回路に 1 を出力させる入力があるか否かは，
すなわち M に入力 x を与えたとき遷移 t 回以内で受理させる乱数列 r があるか否かであ
るから，確かにこの函数 T は timeNSim から circSat への多対一帰着になっている．
5-3
circSat が NP 完 なので問 3.7 より sat や 3sat も NP 完 である（クックの定理）．
is（→問 3.6）は，与えられた無向グラフ G と正整数 l とに対し，G に大きさ l 以上の独
立集合があるか判定する問題であった．
B
問 5.2
s
函数 T を各 3CNF 式 ϕ =
i=1
(li1 ∨ li2 ∨ li3 ) に対し T (ϕ) = (Gϕ , s) となるもの
とする．但し Gϕ とは，各リテラル出現 lij に対応して頂点 vij をもち，辺を次の二つの
場合に設けて得られるグラフである．
• 各節 i に対し，vi1 vi2 ，vi2 vi3 ，vi3 vi1 は辺である．
• 各変数 x と，lij = x なる各 i，j と，li′ ,j ′ = ¬x なる各 i′ ，i′ とに対し，vij vi′ j ′ は
辺である．
このとき T が 3sat から is への多対一帰着であることを示せ．
このような T を多項式時間で計算できるから 3sat ≤FP
m is．故に is も NP 完 である．
に問 3.6 より vc や clq も NP 完
A
問 5.3
である．
正整数からなる有限集合が与えられたとき，これを二つの集合に重なりなく
してそれぞれの和を等しくできるか判定する問題 partition は，NP 完
知られる．これを
って次の問題 knapsack が NP 完
割
であることが
であること示せ．
knapsack の個例は品物の有限集合 U と正整数 B ，K ∈ N との組であって各品物
u ∈ U について重量 s(u) ∈ N と価値 v(u) ∈ N が定まったものである．これに対して
u∈S
s(u) ≤ B
（重量の和が背嚢の容量 B を超えない）かつ
u∈S
v(u) ≥ K
（価値の和が目標値 K に達する）なる S ⊆ U が存在するかを判定する．
C
問 5.4
6
hc は与えられた無向グラフ G にハミルトン閉路（すべての頂点を一度づつ通る
閉路）が存在するか判定する問題である．longestCycle は，無向グラフ G と正整数 k
が与えられたとき，G に長さ k 以上の閉路が存在するか判定する問題である．setCover
は，有限集合 X とその部 集合の集まり S と正整数 k とが与えられたとき，大きさ k 以
下の C ⊆ S であって，X の任意の元が C の或る元に属するようなものが，存在するか判
定する問題である．
clq（→問 3.6），hc，vc が NP 完 であることを用いて，longestCycle，setCover，
subgraphIsom（問 4.6 の問題）が NP 完 であることを示せ．
5-4
NP と自己帰着
級 NP や NP 完
C
問題の構造についてもう少し見てゆこう．
問 5.5 判定問題 A が羅列的であるとは，A(x) = 1 なる x が 0n の形をしたものに限ら
15
れることをいう．
P ̸= NP とする．羅列的で NP 完 な判定問題が存在しないことを示せ．
ヒント
問 2.5 のヒントにあるように sat(ϕ) は sat(ϕ0 ) と sat(ϕ1 ) の論理和に等しい．これを
再帰的に
うと sat を解くことはできるが，毎回二手に
かれるから指数的な手間がかか
る（変数 x1 ，…，xi を固定する仕方は 2 通りある）．sat が羅列的な問題に帰着することを
i
用いてこの爆発を抑える．
C
問 5.6
15
ヒント
もし NP ⊆ BPP ならば NP = RP となることを示せ．
問 4.8 のような方法で BPP の誤り確率を著しく減らすことができる．もし NP ⊆ BPP な
らばこのことより sat が低い誤り確率（但し両側誤り）で判定できる．これを片側誤りにし
たい．つまり或る論理式を充足可能と答えるのは本当に充足割当があるのを確かめてからに
したい．そのために問 5.5 のヒントにある ϕ の充足可能性と ϕ0 ，ϕ1 の充足可能性との関係
を繰返し用いる．
C
問 5.7
4＋3＋6＋7
NP ̸= P ならば，NP に属するが P に属せず NP 完 でもない問題が存在する
こと を示そう（図 5.2）．本問では議論の都合上まず約束つき判定問題（→第二回）を扱
*1
い，P や NP も約束つき判定問題からなると考えるが，最後の（4）で結論は約束なし問題
に限っても成立つことを示す．
非減少函数 f : N → N に対し，約束つき判定問題 satf を次で定義する．
dom satf =
satf x10|x|
f (|x|)
f (|x|)
x10|x|
= sat(x)
（1）もし f が有界ならば satf が NP 完
: x ∈ dom sat
(x ∈ dom sat)
であることを示せ．
（2）もし f が有界でなく satf が NP 完 ならば NP = P となることを示せ．問 3.9 を
用いよ．
（3）多項式時間限定の機械をすべて並べた列 M0 ，M1 ，…を一つ取る．各 n ∈ N に対
し，f (n) は次を満す最小の数 i と定める．
*1
R. E. Ladner. On the structure of polynomial time reducibility. Journal of the ACM 22(1):155–
171, 1975.
但し問 5.7 で用いた証明はこの論 とは異なる．
5-5
NP 完
NP 完
NP
NP
P = NP
P
P
図 5.2 NP ̸= P は示されていないが，中央の図の関係にないことはわかっている．
長さ n 未満の任意の
字列 x ∈ dom sat に対し，Mi に x01|x|
f (|x|)
を入力し
たときの出力は sat(x) に等しい．
ここで f (n) の定義に f が現れたが，n 未満での値のみを
（a）この f が有界であるには satf ∈ P が必要十
（b）NP ̸= P ならば satf が P に属せず NP 完
（4）以上により satf は確かに NP \ P に属し NP 完
ったので差支えない．
であることを示せ．
でもないことを示せ．
でないことがわかったが，本来
はそのような約束なし問題の存在を示したいのであった．これを示すため，f の定
義を修正することで，satf から所望の約束なし問題を直ちに得られるようにせよ．
5-6
その他の級の完
同様に PSPACE 完
問題
性も定義できる．すなわち問題 B ∈ PSPACE が PSPACE 完
（PSPACE-complete）であるとは，任意の A ∈ PSPACE に対して A ≤FP
m B が成立つこと
をいう．PSPACE についても問 5.1 と同様のことが成立つ．また timeNSim が NP 完
であったのと同様に，与えられた組 (M, x, 0s ) が次を満すか判定する問題 spaceSim が
PSPACE 完 である．
• 機械 M に 字列 x を入力して動かすと受理し，消費空間は s 以下である．
またこの問題を帰着することにより例えば問 3.5 の判定問題 qbf が PSPACE 完
である
ことが知られている．
一方，P やそれよりも小さい級における完
た所で述べたように，FP を
性を定義するには，第三回に帰着を定義し
って定義した帰着 ≤FP
m は役に立たないので，対数空間の多
対一帰着によって定義した ≤FL
m を
う．問題 B ∈ P が P 完 （P-complete）であるとは，
*2
任意の A ∈ P に対して A ≤FL
m B が成立つことをいう ．
C
問 5.8 機械の動きを表す回路を作る問題 makeCirc（先程 circSat の NP 完
9
性を示
す際に考えた makeNCirc と同じことを決定性機械について考え，乱数列を取らない回
路を出すようにしたもの）は，詳しく見ると FP だけでなく FL に属することがわかる．
これを用いて cEval が P 完
*2
であることを示せ．
FL
本来はどの帰着を うか明示して NP-≤FP
m 完 ，P-≤m 完 などと言うべきだが省くことが多い．本演
FP
習で現れた NP-≤m 完 問題はみな，実はほぼ同じ帰着により NP-≤FL
m 完 でもある．
5-7
問題 B ∈ NL が NL 完 （NL-complete）
であるとは，任意の A ∈ NL に対して A ≤FL
m B
が成立つことをいう．
C
問 5.9
dPath（→問 4.11）が NL 完 であることを示せ．先程 circSat の NP 完 性
8
を示す際に考えた makeNStep や makeNCirc が FL に属することは用いてよい．
ヒント 「乱択機械の時点表示を頂点とし遷移関係を辺とする有向グラフを考える」
注意
C
この「ヒント」はあくまでヒントなので
問 5.10
4＋4
う場合はきちんと説明すること．
（1）問 5.9 と問 4.11（2）とから NL ⊆ DSpace((log n)2 ) を示せ．
（2）問 5.9 と問 4.12 とから NL = coNL を示せ．
C
問 5.11
6
問 5.10（1）を用いて PSPACE = NPSPACE を示せ．但し NPSPACE は多項式空
間限定の機械により N 決定される判定問題の
体を表す．
ヒント 「水増し」（→問 3.9）
C
問 5.12
11
2sat が NL 完 であることを示せ．問 2.4（1）や問 5.10（2）の結果を用いると
きは明示せよ．
締切（事務室印有効）
A
12 月 5 日（金）
B
12 月 12 日（金）
C
1 月 16 日（金）
5-8
© Copyright 2024 ExpyDoc
