最適化問題の「P」と「NP」をちゃんと理解したい
問題のクラス
計算量の話
計算量には大きく時間と空間の2通りの評価基準があります。
- 時間計算量 / 時間量
計算を終えるまでに要する基本演算の回数。 - 空間計算量 / 領域量
計算の途中経過を一時保存するのに要する記憶領域。
計算量の増加の「速さ」
アルゴリズムの「良さ」を評価する指標の一つに、入力されたデータの長さ
微分積分学における「極限」の概念によれば、多項式は平方根よりも速く、指数関数は多項式よりも速く、階乗は指数関数よりも速く発散します:
特筆すべき点は、発散の速さは最も発散が速い項に影響を受けることです。他にどんなに沢山項があっても、1つでも発散の速い項が存在すれば、式全体として発散が早くなるのです。そこで、アルゴリズムの計算量の増大の速さを評価する際には、もっとも発散の速い項にのみ着目します。
さらに、定数倍の違いはグラフの縦軸方向の定数倍の変化でしかなく、グラフの曲線の形状そのものは変化しないと考えて、切り捨てて考えます。
スターリングの公式
指数よりも階乗のほうが発散が速いことは、次のスターリングの公式からわかります。
ここで、
オーダー記法
以上の考え方をもう少し一般化したのが、ビッグオー記法と呼ばれるものです。この記事では「オーダー記法」と呼ぶことにします。
定義
ある計算量が、式
であるとは、
を意味します。
注意事項
定義の記号の使い方から分かるように、
したがって、本来は記号「
しかしながら、計算理論の分野では専ら「
なのでこの記事でも、以降は特に必要のない限り「
問題の難しさについて
ここまでの計算量の考え方を利用することで、ある (原理的に古典コンピュータで取り扱うことが可能な) 問題の難しさについての議論ができるようになります。
問題の難しさの考え方
次のような順序で考えます。
- 入力データの長さは一律で
とする。N - ある具体的な問題
に対するアルゴリズムI の時間計算量をA で表すことにする。T_A(I)
T_A(I) = \text{($A$ で $I$ を解く際の計算時間)} - ある問題
に対するアルゴリズム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) - ある問題
の時間計算量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) - 以上をまとめると、問題
の難しさは、「最も時間がかかる具体例 を 最も高速に解くアルゴリズム の時間計算量」で定義される。Q
T(Q) = \min_{A \in A(Q)} \max_{I \in Q} T_A(I) - 特に、「
が大きくなるにつれてどれほど計算時間が長くなるのか」に興味があるので、N のとき、次のように言うことが多い。T(N) = \mathcal O(f(N))
\text{「問題 $Q$ の難しさは } \mathcal O(f(N)) \text{」}
ごちゃごちゃしてきたので整理しましょう。
記号 | 意味 | 内容 |
---|---|---|
入力データの長さ | ||
問題 | 「線形計画問題」「ナップサック問題」など | |
問題の具体例 | ||
アルゴリズム | 「内点法」など | |
|
||
|
||
|
このようにして求められた
注意事項
ここで、次の2点に注意しましょう。
-
アルゴリズム
には、問題A が確実に解けるアルゴリズム (厳密解法) のみが採用されることQ
「確実に解けるアルゴリズム」であるには、得られた解が本当に正しい解である保証が必要です。 -
最も時間がかかるようなインスタンスについて論じているということ
逆に言えば、「一般的には非常に難しい」とされているような問題でも、ある範囲の問題について考えればそれほど難しくないというケースもよくあります。たとえば整数計画法の最適化問題は一般にNP困難とされますが、すべての問題が非常に難しいわけでもなく、それほど時間を掛けなくても厳密に解けるような問題が割とたくさん含まれています。
極端なことを言えば、最適化問題に対して、適当に解を1つ持ってきて、「これが解である! たとえ実行可能解でなくとも」といえば、すべての最適化問題が
たとえば、メタヒューリスティクス (進化的プログラミング、タブーサーチ (TS)、シミュレーテッドアニーリング (SA)など) は、理想的なコンディションにおいては、高速に最適解 (に近い解) を求めることができる可能性があります。しかし、そのようにして得られた解が大域的最適解である保証はどこにもありませんし、あるインスタンスにはよく効くけれど、あるインスタンスには全く効果がないというような場合も往々にしてあります (少し前に話題が過熱して、挙げ句の果てに炎上した「量子アニーリング (QA)」もこの一種です)。
定数時間、多項式時間、指数時間など
計算時間については、次のような名称を使うことがあります。
オーダー | 名称 | 概要 |
---|---|---|
定数時間 | 問題の長さに関わらず計算時間が一定。基本的に一瞬で解ける。 | |
対数時間 | 問題の長さが長くなるほど増大がゆっくりになる。解ける場合が多い。 | |
線形時間 | 問題の長さに比例して計算時間が長くなるもの。産業界ではこれが基準になるらしい。 | |
準線形時間 | 線形時間よりちょっと遅い。学術界で基準になることが多い。 | |
多項式時間 | 問題の長さ |
|
指数時間 | 問題の長さ |
|
階乗時間 |
|
問題の難しさのクラス
問題の難しさのクラス
-
/ polynomial time:\rm P Q_D \in \text{P}
ある入力の大きさ に対して、多項式時間N で解を得られるような決定問題\mathcal O(N^k) のクラス。Q_D -
/ non-deterministic polynomial time:\rm NP 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困難を次のように定義します。
-
完全 / NP-complete:\rm NP Q_D \in \text{NP-complete}
クラス に属する任意の決定問題\rm NP が帰着可能な決定問題Q_D' のクラス。Q_D -
困難 / NP-hard:\rm NP Q \in \text{NP-hard}
クラス に属する任意の決定問題\rm NP が帰着可能な問題Q_D' のクラス。Q
なお、定義から明らかに
最適化問題とNP完全・NP困難
このままでは
\rm NP 問題
ある具体的な最適化問題
ある巡回セールスマン問題
には、長さが Q 以下となる巡回路が存在するか? (存在するならば K 、存在しないならば \rm yes ) \rm no
ある種の決定問題
巡回セールスマン問題の決定問題「長さが
以下となる巡回路が存在するか?」において、それが K となる証拠となる巡回路が与えられたとする。 \rm yes
決定問題がであることを確認するには、実際に与えられた巡回路の長さを計算して、それが \rm yes 以下であることを確かめればよい。これは、巡回路の式の 大きさ K (巡回路の 長さ ではない) についての多項式時間で計算できる。 N
このような種類の決定問題
NP完全問題
ある決定問題
- 問題
はQ_D に含まれる\rm NP - クラス
に含まれる任意の問題\rm NP が問題Q_D' に帰着可能であるQ_D
決定問題
- まず、既に
完全であることが証明された問題を用意する。\rm NP クック・レビンの定理
充足可能性問題 (satisfiability problem; SAT) は 完全である。\rm NP - 次に、問題を順次帰着させていく。
NP困難
基本的に、ある最適化問題
ある巡回セールスマン問題
が解ければ、問題 Q に対する最短路の長さも求められたことになるので、決定問題 Q 「問題 Q_D には長さ Q 以下の巡回路は存在するか?」も解かれたことになる。 K
したがって、最適化問題
なお、最適化問題
- 決定問題を作成する
- 決定問題がNP完全問題であることを示す
NP完全か、NP困難か
ある最適化問題について調べるとき、それがNP完全なのかNP困難なのかが、資料によってまちまちなことがあります。このような場合は大抵、
- 最適化問題は NP困難
- 決定問題は NP完全
と読み替えれば間違いないです。
参考文献
梅谷俊治, 「しっかり学ぶ数理最適化」, 講談社 (2020).
Discussion