🙄

クラス P の意味がいまいちピンと来なかった話

2023/04/13に公開

クラスp

クラスnp

tech

はじめに

クラス P、クラス NP・・・などの話題を、情報工学の分野にいると聞くことがあります。

「クラス P って何だっけ？」と思い、その都度調べて「ふーん」と感じる程度で、きちんと理解していませんでした。

この記事では、それぞれのクラスの意味と、その延長にある $N \neq NP$ 問題の概要についてまとめます。

時間計算量について

時間計算量は、 $O$ という記法を使って表します。例えば、長さ $n$ のリストを並び替えるアルゴリズム $A$ があると仮定します。長さ $n$ が 2 倍になったときに、並び替えにかかる時間も 2 倍になった場合、このアルゴリズム $A$ は、 $O(n)$ のオーダーを持つと表すことができます（アルゴリズム $A$ の時間計算量は $n$ に比例することを意味します）。また、オーダーが $O(n^2)$ である別の並び替えアルゴリズム $B$ があるとします。アルゴリズム $B$ の時間計算量は $n^2$ に比例します。つまり、 $n$ が 2 倍になると、計算にかかる時間が 4 倍になります。

一般に、あるアルゴリズムのオーダーが $O(n^k)$ という形で表される場合、これを多項式オーダーと言い、多項式オーダーを持つアルゴリズムを「多項式計算量を持つアルゴリズム」と言います。

クラス P

オーダーが $O(n^k)$ 以下のアルゴリズムの問題が属するクラスを「多項式（Polynomial）時間計算可能なクラス -> クラス P」と呼びます。つまり、多項式計算量を持つアルゴリズムは、クラス P に属しています。

決定性について

クラス NP の説明で「非決定性・・・」といきなり出てくるので、ここで決定性とは何かを説明しておきます。クラス P に属しているアルゴリズムは多項式時間で解くことができる決定性（Deterministic）アルゴリズムです。決定性というのは、たった1つの解を求めることができるという性質です。

多項式時間で解ける決定性アルゴリズムを持たない問題、あるいは多項式時間で解ける決定性アルゴリズムがまだ見つかっていない問題は、クラス P には属しません。

多項式時間で解けない場合には、「非決定性（Non-Deterministic）アルゴリズム」 を使用します。非決定性アルゴリズムは、計算途中の分岐先が複数あるようなアルゴリズムです。

厳密な解を出そうとするのが決定性アルゴリズムです。厳密な解を出すにはあまりにも時間がかかってしまうので、解の候補をいくつか出すのが非決定性アルゴリズムです。

例えば、自宅から職場に通勤するのに一番時間がかからない経路を見つけたいとします。

クラス NP

クラス P に属さないような問題を多項式時間内で解くには、まず解の候補を見つけることを非決定的に行います。次にその候補が正しい解かどうかを決定性アルゴリズムを使用して確認します。このように解くことのできる問題をクラス NP（Non-Deterministic）と言います。

クラス P とクラス NP の関係

クラス P とクラス NP の違いは、決定性アルゴリズムによって多項式時間で解ける（クラス P）か、解けない（クラス NP）か、です。クラス P は、複数解の選択肢を持たない非決定性アルゴリズムで解ける問題と見なすことができるので、クラス P は、クラス NP の部分集合と見なすことできます。

P \subseteq NP

クラス NP とクラス P が等しいかどうかは、まだ証明されていません。クラス NP の問題は、多項式時間で解ける決定性アルゴリズムが見つかっていないだけで、本当はクラス P として解けるかもしれません。つまり、現在クラス NP とされている全ての問題に必ず多項式時間内で解ける決定性アルゴリズムがあることが証明されると、 $P=NP$ が証明されます。

NP 完全

ある問題 $A$ が、以下の条件を満たすとき、 $A$ を NP 完全といいます。

クラス NP に属する
クラス NP に属する他の全ての問題が多項式時間内で $A$ に変換できる

ある問題 $A$ が NP 完全とします。また、 $A$ を解く決定性多項式時間アルゴリズムが求めることができた（ $A$ はクラス P であるとわかった）場合、全てのクラス NP の問題はクラス P になります。

NP 困難

NP 完全の定義のうち、2. は証明できても 1. が証明できないとき、その問題を NP 困難であるといいます。