定理 8.2. U ={u1, . . . , un}, (a1, p1), . . . ,(an, pn)∈R+×R+,b∈R+を入力とする．∀i∈[n][ai ∈ Z+]かつ W = max{a1, . . . , an} のとき，ナップサック問題は O(nW) 時間で（正確に）解くこと ができる．
問 8.6. 上で示されたアルゴリズムにおいて，∀i∈[n][ai∈Z+]である理由を説明しなさい．
系 8.1. W =poly(n) のとき，ナップサック問題は（nの）多項式時間で解くことができる．
この定理（及び系）は，ナップサック問題が疑多項式時間で解けることを示している．実際には，
以下の補題を用いて，ナップサック問題が FPTASをもつことが示される．
補題 8.2. U ={u1, . . . , un}, (a1, p1), . . . ,(an, pn)∈R+×R+,b∈R+ を入力とする．∀i∈[n][pi ∈ Z+]かつP = max{p1, . . . , pn}のとき，ナップサック問題はO(n2P)時間で（正確に）解くことが できる．
証明. 次のような関数 S: [n]×[nP]→2[n] を考える．任意のi∈[n], p∈[nP]について，
S(i, p) def= arg min
S⊆[i]
∑
j∈S
aj : ∑
j∈S
pj =p
. ただし，ここでは，任意のp∈[nP]に対して∑
j∈∅aj =pが成り立ち，その場合，∑
j∈∅aj =∞と 定義する．このとき，以下の漸化式が成り立つ．
S(i, p) =
arg min
S∈{S(i−1,p),S(i−1,p−pi)}
∑
j∈S
aj
: pi≤p
S(i−1, p) : pi> p
(4)
問 8.7. 漸化式 (4)が成り立つことを示しなさい．
このとき，最適解は以下となる．
arg max
S(n,p):p∈[nP]
p : ∑
j∈S(n,p)
aj ≤b
. (5)
問 8.8. 最適解が (5)で表されることを示しなさい．
以上より，図12のアルゴリズムによって最適解が求められる．（以下のアルゴリズムでは，∑
j∈∅aj = nP + 1とする．）
入力：集合U ={u1, . . . , un}, (a1, p1), . . . ,(an, pn)∈R+×R+,b∈R+，ただし，∀i∈[n][pi∈Z+] 1. S(1, p1) ={1}，それぞれの p∈[nP]\ {p1}について S(1, p) =∅ とする．
2. それぞれのi∈[n]\ {1},p∈[nP]について以下を実行する．
(a) pi ≤p の場合，X =S(i−1, p), Y =S(i−1, p−pi)∪ {i} として，∑
j∈Xaj ≤∑
j∈Y aj
なら S(i, p) =X，そうでないならS(i, p) =Y とする．
(b) pi > p の場合，S(i, p) =S(i−1, p) 3. 式(5) を求める．
図12: ナップサック問題を解くアルゴリズム
関数 S の定義域[n]×[nP]の大きさはn2P であることから，アルゴリズムの計算時間はO(n2P)
である． ■
問 8.9. 図12 のアルゴリズムを，以下のように再帰関数 RS(i, p) を用いて記述した．
• それぞれのp∈ {nP, nP −1, nP−2, . . . ,2,1}について（降順に）以下を実行する．
1. S =RS(n, p) とする．（再帰関数RS(n, p) を実行する．） 2. ∑
i∈Sai≤bであれば S を出力して終了する．
このとき，RS(i, p) の疑似コードを記述しなさい．
定理 8.3. ナップサック問題はFPTASをもつ．
入力：集合U ={u1, . . . , un}, (a1, p1), . . . ,(an, pn)∈R+×R+,b∈R+,ϵ >0 1. P = max{p1, . . . , pn}として K =P·(ϵ/n)とする．
2. p′i =⌊pi/K⌋ として，上の定理で示されたアルゴリズムA を実行する．
3. A の出力を出力する．
図13: ＦＰＴＡＳアルゴリズム
証明. 図 13 のアルゴリズムの出力をS，最適解を S∗ とする．(1−ϵ)val(S∗)≤val(S) を示せば十 分である．（十分小さなϵ > 0に対して，val(S∗)/val(S)≤1/(1−ϵ)≤1 + 2ϵ なので．）p′i の定義よ り，任意の i∈[n]について，
p′iK ≤ pi ≤ p′iK+K.
また，{p′1, . . . , p′n} においてS は最適解であるから，∑
i∈Sp′i ≥∑
i∈S∗p′i．これらより，
val(S) = ∑
i∈S
pi ≥ ∑
i∈S
p′iK ≥ ∑
i∈S∗
p′iK ≥ ∑
i∈S∗
(pi−K)
≥ ∑
i∈S∗
pi−nK (∵ |S∗| ≤n)
= val(S∗)−nK.
よって，（K =P ·(ϵ/n)，val(S∗)≥P より）
val(S) ≥ val(S∗)−nK = val(S∗)−ϵP ≥ val(S∗)−ϵval(S∗) = (1−ϵ)val(S∗).
アルゴリズムの計算時間は，P′= max{p′i}=n/ϵより，O(n2P′) =O(n3/ϵ)である． ■
9 充足可能性問題
定義9.1
X を論理変数の集合とする．任意の変数x∈X について，x 及びx¯ をリテラルという．い くつかのリテラルを論理和 ∨で結合したものを節という．節をなすリテラルの個数をその節の 大きさという．いくつかの節を論理積∧ で結合したものを和積標準形（CNF）論理式という．
特に，すべての節の大きさがk 以下であるとき，k-CNF論理式という．
例 9.1 (充足可能性問題). 以下の φは，変数 x1, x2, x3, x4, x5 上の 3-CNF 論理式である．
φ = x1∧(¯x1∨x2)∧(x1∨x¯2∨x¯3)∧(¯x1∨x¯3∨x4)∧x¯2∧(¯x3∨x¯4∨x¯5).
事実 9.1. 任意の論理関数f :{0,1}n→ {0,1}は，CNF論理式で表される．
以降では，CNF 論理式は，記号∧ を省略して表記する．例えば，上のφ は以下のように表記さ れる．
φ = x1(¯x1∨x2)(x1∨x¯2∨x¯3)(¯x1∨x¯3∨x4)¯x2(¯x3∨x¯4∨x¯5).
また，CNF 論理式を，節の集合とみなすこともある．例えば，上のφは以下のように表記される．
φ = {x1,(¯x1∨x2),(x1∨x¯2∨x¯3),(¯x1∨x¯3∨x4),x¯2,(¯x3∨x¯4∨x¯5)}.
よって，C がφの節であるとき，C∈φと表記する．また，|φ|は節の個数になる．（節に関しても 同様である．例えば，x¯ が節C のリテラルであるとき，x¯∈C と表記する．）
定義9.2
φをX 上の任意のCNF論理式，C をφの任意の節とする．t:X→ {0,1} をX への任 意の真理値割り当てとする．割り当てtのもとで節C が真になるとき，C がtにより充足する という．
充足可能性問題（satisfiability）
• 入力：X 上のCNF 論理式φ
• 解：X への真理値割り当てt:X → {0,1}
• 最大化：tにより充足する φの節の個数
例 9.2. 先の例の 3-CNF 論理式 φ において（|φ|= 6），t(X) = (1,1,1,1,1) により充足するφの 節の個数は4，t(X) = (1,1,1,1,0)により充足するφ の節の個数は 5．
9.1 貪欲法
定理 9.1. 充足可能性問題の近似率は2 である．
入力：X 上の CNF論理式 φ
1. t:X→ {0,1}を未定義とする．（t が出力になる．） 2. それぞれのx∈X について（順次）以下を繰り返す．
(a) P, N ⊆φを以下のように定義する．
P def= {C∈φ:x∈C}, N def= {C∈φ: ¯x∈C}. (b) 以下のようにする．
t(x) = 1, φ=φ\P : |P| ≥ |N|, t(x) = 0, φ=φ\N : o.w.
3. tを出力する．
図 14: 貪欲アルゴリズム
問 9.1. ３変数で５個の節からなる適当な入力を考案して，その入力に対する図14 のアルゴリズム の動作及び出力を示しなさい．
証明. 図 14 のアルゴリズムの出力を t，最適解を t∗ とする．|X| = n とする．アルゴリズムのス テップ 2 の第 i回目（i∈[n]）の繰り返しにおいて，|P| ≥ |N|であるときAi =P,Bi=N，そう でないときAi=N,Bi =P とする．
主張 9.1. 以下の二つが成り立つ．
1. val(t) = ∑
i∈[n]
|Ai| 2. ∪
i∈[n]
(Ai∪Bi) = φ.
問 9.2. この主張を証明しなさい．
この主張より，
val(t) = ∑
i∈[n]
|Ai| = ∑
i∈[n]
|Ai| ·|Ai|+|Bi|
|Ai|+|Bi| = ∑
i∈[n]
|Ai|
|Ai|+|Bi|·(|Ai|+|Bi|)
≥ 1 2
∑
i∈[n]
(|Ai|+|Bi|) (∵ |Ai| ≥ |Bi|)
≥ 1 2
∑
i∈[n]
|Ai∪Bi| (∵ |Ai|+|Bi| ≥ |Ai∪Bi|)
≥ 1 2 ∪
i∈[n]
(Ai∪Bi)
(∵ 上と同等の理由)
= 1 2 · |φ|
≥ val(t∗) 2 .
よって，val(t∗)/val(t)≤2． ■
問 9.3. 図14 のアルゴリズムの近似率が 2となる入力の例をあげなさい．