最適化問題の「P」と「NP」をちゃんと理解したい

問題のクラス $\rm P$ と $\rm NP$ についての理解が曖昧なことに気づいたので、ちょっと勉強しました。忘れてもいいようにメモしておきます。

計算量の話

計算量には大きく時間と空間の2通りの評価基準があります。

• 時間計算量 / 時間量
  計算を終えるまでに要する基本演算の回数。
• 空間計算量 / 領域量
  計算の途中経過を一時保存するのに要する記憶領域。

計算量の増加の「速さ」

アルゴリズムの「良さ」を評価する指標の一つに、入力されたデータの長さ $N$ が大きくなるとき、要求される時間 (または領域) がどれほどの速さで増加していくかというものがあります。

微分積分学における「極限」の概念によれば、多項式は平方根よりも速く、指数関数は多項式よりも速く、階乗は指数関数よりも速く発散します:

$${}^\forall k, a \in \mathbb R_+, {}^\exists \bar N: \bar N \lt N \implies N^k \lt a^N \lt N!$$

特筆すべき点は、発散の速さは最も発散が速い項に影響を受けることです。他にどんなに沢山項があっても、1つでも発散の速い項が存在すれば、式全体として発散が早くなるのです。そこで、アルゴリズムの計算量の増大の速さを評価する際には、もっとも発散の速い項にのみ着目します。

$$\begin{align*} & N \log N + 3N + \sqrt{N} &&\to && N \log N \\ & 2^N + N^9 + N^3 &&\to && 2^N \\ & 2N! + 2^N + 5 && \to && 2N! \end{align*}$$

さらに、定数倍の違いはグラフの縦軸方向の定数倍の変化でしかなく、グラフの曲線の形状そのものは変化しないと考えて、切り捨てて考えます。

$$\begin{align*} & 2N! &&\to &&N! \\ & N \log 3 && \to && N \\ & a N \log N && \to && N \log N \end{align*}$$

スターリングの公式

指数よりも階乗のほうが発散が速いことは、次のスターリングの公式からわかります。

$$N! \simeq \sqrt{2 \pi n} \left(\frac{N}{e}\right)^N$$

ここで、$\simeq$ は $N \to \infty$ において両者が一致することを意味します。

オーダー記法

以上の考え方をもう少し一般化したのが、ビッグオー記法と呼ばれるものです。この記事では「オーダー記法」と呼ぶことにします。

$$\begin{align*} & N \log N + 3N + \sqrt{N} &&= && \mathcal O(N \log N) \\ & 2^N + N^9 + N^3 &&= && \mathcal O(2^N) \\ & 2N! + 2^N + 5 &&= && \mathcal O(N!) \end{align*}$$

定義

ある計算量が、式 $T(N)$ で書けるとき、

$$T(N) \in \mathcal O(f(N))$$

であるとは、

$${}^\exists c \in \mathbb R_+, {}^\exists \overline N \in \mathbb Z_+: N \ge \overline N \implies T(N) \le cf(N)$$

を意味します。

注意事項

定義の記号の使い方から分かるように、$\mathcal O(f(N))$ は本来は無限集合であり、$T(N)$ は $\mathcal O(f(N))$ の元です。しかも、ある $\mathcal O(f(N))$ は、それよりも発散の速い元を含む別の $\mathcal O(g(N))$ の部分集合となっています:

$$\begin{align*} &\mathcal O(N) &&\subseteq &\mathcal O(N \log N) \\ &\mathcal O(N \log N) &&\subseteq &\mathcal O(N^2) \\ &\mathcal O(N^2) &&\subseteq &\mathcal O(2^N) \\ &\mathcal O(2^N) &&\subseteq &\mathcal O(N!) \\ \mathrm{i.e.} \quad &\mathcal O(N) &&\subseteq &\mathcal O(N!) \\ \end{align*}$$

したがって、本来は記号「$\in$」を用いて次のように書くべきです:

$$\begin{align*} & N \log N + 3N + \sqrt{N} &&\in && \mathcal O(N \log N) \\ & 2^N + N^9 + N^3 &&\in && \mathcal O(2^N) \\ & 2N! + 2^N + 5 &&\in && \mathcal O(N!) \end{align*}$$

しかしながら、計算理論の分野では専ら「$=$」を使用するようです。

$$\begin{align*} & N \log N + 3N + \sqrt{N} &&= && \mathcal O(N \log N) \\ & 2^N + N^9 + N^3 &&= && \mathcal O(2^N) \\ & 2N! + 2^N + 5 &&= && \mathcal O(N!) \end{align*}$$

なのでこの記事でも、以降は特に必要のない限り「$=$」を使用します。

問題の難しさについて

ここまでの計算量の考え方を利用することで、ある (原理的に古典コンピュータで取り扱うことが可能な) 問題の難しさについての議論ができるようになります。

問題の難しさの考え方

次のような順序で考えます。

1. 入力データの長さは一律で $N$ とする。
2. ある具体的な問題 $I$ に対するアルゴリズム $A$ の時間計算量を $T_A(I)$ で表すことにする。
   
   $$T_A(I) = \text{($A$ で $I$ を解く際の計算時間)}$$
3. ある問題 $Q$ に対するアルゴリズム $A$ の時間計算量 $T_A(Q)$ は、問題 $Q$ の具体例 $I_1, I_2,\cdots \in Q$ の中から、最も計算に時間がかかる具体例 $I$ に対する時間計算量 $T_A(I)$ とする。
   
   $$T_A(Q) = \max_{I \in Q} T_A(I)$$
4. ある問題 $Q$ の時間計算量 $T(Q)$ は、問題 $Q$ を解くアルゴリズム $A_1, A_2, \cdots \in A(Q)$ の中から、最も高速なアルゴリズム $A$ を用いた際の計算時間量 $T_A(Q)$ とする。
   
   $$T(Q) = \min_{A \in A(Q)} T_A(Q)$$
5. 以上をまとめると、問題 $Q$ の難しさは、「最も時間がかかる具体例 を 最も高速に解くアルゴリズム の時間計算量」で定義される。
   
   $$T(Q) = \min_{A \in A(Q)} \max_{I \in Q} T_A(I)$$
6. 特に、「$N$ が大きくなるにつれてどれほど計算時間が長くなるのか」に興味があるので、$T(N) = \mathcal O(f(N))$ のとき、次のように言うことが多い。
   
   $$\text{「問題 $Q$ の難しさは } \mathcal O(f(N)) \text{」}$$

ごちゃごちゃしてきたので整理しましょう。

記号	意味	内容
$N$	入力データの長さ
$Q$	問題	「線形計画問題」「ナップサック問題」など
$I$	問題の具体例
$A$	アルゴリズム	「内点法」など
$T_A(I)$	$I$ を $A$ で解くときの計算時間
$T_A(Q)$	$Q$ のうち最も難しい問題を $A$ で解くときの計算時間	$\max_{I \in Q} T_A(I)$
$T(Q)$	$Q$ を解くことができるアルゴリズムのうち、最も高速なアルゴリズムで、$Q$ のうち最も難しい問題を解くときの計算時間	$\min_{A \in A(Q)} \max_{I \in Q} T_A(I)$

このようにして求められた $T(Q)$ (をオーダー記法で表現したもの) を「問題 $Q$ の難しさ」と呼ぶことになります。

注意事項

ここで、次の2点に注意しましょう。

1. アルゴリズム $A$ には、問題 $Q$ が確実に解けるアルゴリズム (厳密解法) のみが採用されること
   「確実に解けるアルゴリズム」であるには、得られた解が本当に正しい解である保証が必要です。
2. 最も時間がかかるようなインスタンスについて論じているということ
   逆に言えば、「一般的には非常に難しい」とされているような問題でも、ある範囲の問題について考えればそれほど難しくないというケースもよくあります。たとえば組合せ最適化問題の1つである Sherrington-Kirkpatrick モデル (SK模型) の基底状態探索問題は、最悪計算量はおそらく $\mathcal O(2^N)$ と信じられていますが、平均的には多項式 $\mathcal O(N^z)$ で抑えられることが知られています [Montanari+ (2021)]

極端なことを言えば、最適化問題に対して、適当に解を1つ持ってきて、「これが解である! たとえ実行可能解でなくとも」といえば、すべての最適化問題が $\mathcal O(1)$ となってしまいます。これではダメですね。なので、厳密解法のみについて論じる必要があるのです。

たとえば、メタヒューリスティクス (進化的プログラミング、タブーサーチ (TS)、シミュレーテッドアニーリング (SA)など) は、理想的なコンディションにおいては、高速に最適解 (に近い解) を求めることができる可能性があります。しかし、そのようにして得られた解が大域的最適解である保証はどこにもありませんし、あるインスタンスにはよく効くけれど、あるインスタンスには全く効果がないというような場合も往々にしてあります。

定数時間、多項式時間、指数時間など

計算時間については、次のような名称を使うことがあります。

オーダー	名称	概要
$\mathcal O(1)$	定数時間	問題の長さに関わらず計算時間が一定。基本的に一瞬で解ける。
$\mathcal O(\log N)$	対数時間	問題の長さが長くなるほど増大がゆっくりになる。解ける場合が多い。
$\mathcal O(N)$	線形時間	問題の長さに比例して計算時間が長くなるもの。産業界ではこれが基準になるらしい。
$\mathcal O(N \log N)$	準線形時間	線形時間よりちょっと遅い。学術界で基準になることが多い。
$\mathcal O(N^k)$	多項式時間	問題の長さ $N$ に対して、計算時間が多項式オーダーで増加。解けるものが多い領域と解けないものが多い領域の境界線という感じ。
$\mathcal O(k^N)$	指数時間	問題の長さ $N$ に対して、計算時間が指数関数的に増加。ちょっとやばい。
$\mathcal O(N!)$	階乗時間	$N$ の階乗に比例して計算時間が爆発的に増加。基本的に小規模なものしか解けないと思って良い。

問題の難しさのクラス

問題の難しさのクラス $\rm P$ と $\rm NP$ を次のように定義します。

• $\rm P$ / polynomial time: $Q_D \in \text{P}$
  ある入力の大きさ $N$ に対して、多項式時間 $\mathcal O(N^k)$ で解を得られるような決定問題 $Q_D$ のクラス。
• $\rm NP$ / non-deterministic polynomial time: $Q_D \in \text{NP}$
  $Q_D = \rm yes$ であることの証拠となる、大きさ $N$ の具体的な入力 $I_N$ が与えられたとき、実際に $Q_D = \rm yes$ であることを多項式時間 $\mathcal O(N^k)$ で確認できるような決定問題 $Q_D$ のクラス。
  「NP」は非決定性チューリング機械 (non-deterministic Turing machine)で多項式時間 (polynomial time) で解ける決定問題であることに由来する。「多項式時間で解けない」という意味ではない。

また、NP完全とNP困難を次のように定義します。

• $\rm NP$ 完全 / NP-complete: $Q_D \in \text{NP-complete}$
  クラス $\rm NP$ に属する任意の決定問題 $Q_D'$ が帰着可能な決定問題 $Q_D$ のクラス。
• $\rm NP$ 困難 / NP-hard: $Q \in \text{NP-hard}$
  クラス $\rm NP$ に属する任意の決定問題 $Q_D'$ が帰着可能な問題 $Q$ のクラス。

なお、定義から明らかに $\rm P \subseteq NP$ です。一方で $\rm NP \subseteq P$ か否かは証明されていません (証明が非常に困難であることはわかっています)。人類の長年の努力にも関わらず 多項式時間で解けるアルゴリズムが発見されていないNP問題が数多く存在する という現状から、おそらく $\rm NP \nsubseteq P$ であり、ゆえに $\rm P \ne NP$ であろうと言われています。これを $\rm P \ne NP$ 予想と言います。

最適化問題とNP完全・NP困難

このままでは $\rm NP$ 問題についてちょっと理解しにくいので、最適化問題に絞って、もう少し具体的に見てみます。

$\rm NP$ 問題

ある具体的な最適化問題 $Q$ に対して、それがある性質を満たすかを問う問題 $Q_D$ を、決定問題と呼びます。

ある巡回セールスマン問題 $Q$ には、長さが $K$ 以下となる巡回路が存在するか? (存在するならば $\rm yes$、存在しないならば $\rm no$)

ある種の決定問題 $Q_D$ については、それが $\rm yes$ か否かを、入力の大きさ $N$ についての多項式時間 $\mathcal O(N^k)$ で判定できる場合があります。

巡回セールスマン問題の決定問題「長さが $K$ 以下となる巡回路が存在するか?」において、それが $\rm yes$ となる証拠となる巡回路が与えられたとする。
決定問題が $\rm yes$ であることを確認するには、実際に与えられた巡回路の長さを計算して、それが $K$ 以下であることを確かめればよい。これは、巡回路の式の 大きさ $N$ (巡回路の 長さ ではない) についての多項式時間で計算できる。

このような種類の決定問題 $Q_D$ は、クラス $\rm NP$ に含まれるといいます。

NP完全問題

ある決定問題 $Q_D$ が次の2つの条件を満たすとき、$Q_D$ はクラス $\rm NP$ に属す問題の中で最も難しい問題であるという意味で、NP完全 であるといいます。

1. 問題 $Q_D$ は $\rm NP$ に含まれる
2. クラス $\rm NP$ に含まれる任意の問題 $Q_D'$ が問題 $Q_D$ に帰着可能である

決定問題 $Q_D$ がNP完全問題であることを示すには、次のような手順を踏みます。

1. まず、既に $\rm NP$ 完全であることが証明された問題を用意する。

   クック・レビンの定理
   充足可能性問題 (satisfiability problem; SAT) は $\rm NP$ 完全である。

2. 次に、問題を順次帰着させていく。

$$\small \begin{align*} (\text{SAT}) &\le (\text{頂点被覆問題}) \\ &\le (\text{無向ハミルトン閉路問題}) \\ &\le (\text{巡回セールスマン問題の決定問題}) \end{align*}$$

NP困難

基本的に、ある最適化問題 $Q$ から作成される決定問題 $Q_D$ は、元の最適化問題が解ければ自動的に解けることになります。

ある巡回セールスマン問題 $Q$ が解ければ、問題 $Q$ に対する最短路の長さも求められたことになるので、決定問題 $Q_D$「問題 $Q$ には長さ $K$ 以下の巡回路は存在するか?」も解かれたことになる。

したがって、最適化問題 $Q$ は、決定問題 $Q_D$ よりも難しいと言うことができます。そこで、$Q_D$ がNP完全問題である場合、$Q$ はNP完全問題と同等か、それ以上に難しい問題という意味で、NP困難 であるといいます。

なお、最適化問題 $Q$ がNP困難であることを示すには、次のステップを踏みます。

1. 決定問題を作成する
2. 決定問題がNP完全問題であることを示す

NP完全か、NP困難か

ある最適化問題について調べるとき、それがNP完全なのかNP困難なのかが、資料によってまちまちなことがあります。このような場合は大抵、

• 最適化問題は NP困難
• 決定問題は NP完全

と読み替えれば間違いないです。

参考文献

[Umetani (2020)] 梅谷俊治, 「しっかり学ぶ数理最適化」, 講談社 (2020).
[Montanari+ (2021)] K. Atarashi, S. Oyama, and M. Kurihara, (2021).