東大 生物情報学科、学部生の備忘録

東京大学の学生です。日々の気づき、学び、つまづいたことをメモにします。

MENU

ナップサック問題（判定版）が弱NP完全問題であることの証明

情報科学・数学

はじめに

定期テストに向けて、Karp's Reduction の流れに沿って、諸々の問題の NP 完全性を示すことができるように勉強する必要が生じた。 ここでは、ナップサック問題が弱 NP 完全問題であることを、Partition が弱 NP 完全問題であることを利用して、証明する。

Partition について

Partition における入力は、 n 個の要素からなる整数集合 S = { a_1, a_2, ..., a_n} である。 出力すべきは、

ある X \subset S で、 \begin{equation} \sum_{i \in X} a_i = \sum_{i \not \in X} a_i \end{equation} を満たす X は存在するか。

である。 見てわかるように、判定問題である。

動的計画法を用いることによって、入力サイズ L(I) = \displaystyle \sum_{i=1}^n a_i と入力の最大値 M(I) = \max (a_i) によって、 O(L(I)M(I)) の計算量で問題を解くことができる。これは一見多項式時間で解けるように見えるのだが、計算量が入力の数の大きさ M(I) に依存するという点で、擬似多項式時間と呼ばれる。

まとめると、Partition は NP 完全問題であり、擬似多項式時間で解くアルゴリズムは存在する。そのことから、Partition は弱 NP 完全問題と呼ばれる。

ナップサック問題（判定版）K の定義

判定版ナップサック問題を以下のように定義する。：

  • 入力：
    • n 個の物品
    • 各物品 i の重さ w_i
    • 各物品 i の価値 v_i
    • ナップサックの容量（重さ） C
    • 目標値 k
  • 出力：
    • ある集合

      \begin{equation} X \subseteq \lbrace 0, 1, ..., n \rbrace \end{equation}

      で、

\begin{equation} \sum_{i \in X} w_i \leq C \text{ and } \sum_{i \in X} v_i \geq k \end{equation}

となる X は存在するか。

ナップサック問題（判定版）K が NP 完全であることの証明

以下の二つを示して初めて、証明できたこととなる。つまり、

  • K は NP 問題
  • K \leq_m Partition となる多項式時間還元が存在する

このことに注意して、判定版ナップサック問題 K が NP 完全であることを証明する。

1. K が NP 問題であることについて

X が与えられたとする。この時、その X が条件を満たすかどうかの判定は、実際に

\begin{equation} \sum_{i \in X} w_i \leq C, \quad \sum_{i \in X} v_i \geq k \end{equation}

を計算して、両者が成り立っていることを確認すれば良い。これは明らかに多項式時間で行えるため、判定版ナップサック問題は明らかに NP 問題である。

2. K が Partition から多項式時間還元が可能であることの証明

任意の Partition 問題があるナップサック問題に多項式時間で変換することができることを示す。

任意の入力 a_1, a_2, ..., a_n を考える。この時、

\begin{align} &^\forall i, \, w_i = a_i \\ &^\forall i, \, v_i = a_i \\ & C =\dfrac{1}{2} \sum_{i=1}^n a_i \\ & k = \dfrac{1}{2} \sum_{i=1}^n a_i \end{align}

と変数を定義する。これは Partition の入力から、ナップサック問題の入力形式への写像であり、多項式時間で計算することは容易である。

この時、集合 X \subseteq \lbrace 0, 1, ..., n\rbrace について、

\begin{align} & \sum_{i \in X} a_i = \sum_{i \not \in X} a_i \\ \Leftrightarrow & \sum_{i \in X} a_i = \dfrac{1}{2} \sum_{i = 1}^n a_i \\ \Leftrightarrow & \sum_{i \in X} a_i \leq \dfrac{1}{2} \sum_{i = 1}^n a_i \text{ and } \sum_{i \in X} a_i \geq \dfrac{1}{2} \sum_{i = 1}^n a_i \\ \Leftrightarrow & \sum_{i \in X} w_i \leq C \text{ and } \sum_{i \in X} v_i \geq k \\ \end{align}

となる。 したがって、任意の Partition 問題はある形の ナップサック問題に還元することができる（多対一）。

まとめると、 任意の Partition は多項式時間還元によって、限られた形のナップサック問題（判定版）に帰着することができる。

3. まとめる

ここまでの議論（1. と 2.）より、 判定版ナップサック問題は NP 完全問題である。

判定版ナップサック問題に擬似多項式時間アルゴリズムがあることについて

よく知られているように、動的計画法によって、ナップサック問題を解くことができる。計算量は、 \begin{equation} O(n \max(w_i)) \end{equation} となり、入力の数値のサイズに依存していることがわかる。この式より、ナップサック問題は擬似多項式次官アルゴリズムを持つ。 したがって、ナップサック問題は弱 NP 完全問題である。

まとめ

判定版ナップサック問題が弱 NP 完全問題であるということがわかった。 導出はそこまで難しくなかったものの、Partition が弱 NP 完全であり、Partition to knapsack が多項式時間還元できたとしても、knapsack 問題が弱 NP 完全であるといい切ってはならないというのが注意点であろう。Partition から多項式時間還元をしたことによって、knapsack 問題の限定された形の問題が擬似多項式時間で解けるということがわかった。ただしそれだけでは、ナップサック全ての問題が擬似多項式時間で解けるということの説明にはなっていない。forall と exists に細心の注意を払って論を進める必要があるのである。

感想

ナップサック問題、競技プログラミングでよく出てくる。 競技プログラミング、一時期ハマったが、結局魅力がわからなくなってしまった。計算量理論の勉強のように、数学によるゴリゴリの理論が僕にはしっくりくる。競技プログラミングや生物学実験については、今後は熱中できないと思うなぁ。。頑張って無縁の世界に挑みたい。

関連記事

ut-bioinformatic.hatenablog.jp

ut-bioinformatic.hatenablog.jp