P, NP, co-NP
問題の区分として P, NP, co-NP の3つの集合を考えます。
- P
- 多項式時間で解ける問題の集合
- c を定数として、 $O(n^c)$ に属する問題の集合。
- ハノイの塔($\Theta(2^n)$)はこの集合に属さない。
- NP
- あるYESを出力するための入力が与えられた時に、その入力が本当にYESを出力するのか多項式時間で確認できる問題の集合
- co-NP
- あるNOを出力するための入力が与えられた時に、その入力が本当にNOを出力するのか多項式時間で確認できる問題の集合
$ \textrm{P} \subset \textrm{NP} , P \subset \textrm{co-NP}$
-
EXP
- 指数時間で解ける問題の集合
- c を定数として、 $O(2^{n^c})$ に属する問題の集合。
- チェスはこの集合に属し、 P には属さない。 テトリスはこの集合に属し、Pに属すか否かはわかっていない。
-
R
- 有限時間で解ける問題の集合。
- 停止問題(与えられたプログラムが停止するか動き続けるか)はこの集合にも属さない。
-
NP-hard
- ある問題AがNP-hardであるとは、任意のNP問題がチューリングリダクションによってAに帰着可能であることをいう
Reduction
AをBにReduceするとは、Aを解くアルゴリズムを、Bを解くアルゴリズムがあるという前提で記述することである。
例）Aを解くアルゴリズムを、Bを解く関数を組み合わせて作る
チューリングリダクション
チューリングマシンにて実行可能なリダクション
ある NP-hard の問題を 問題Aにreduceできれば、AはNP-hardであることがいえる。
問題の例
Satisfiability, SAT
論理式が与えられた時に、その論理式を真にするようなリテラルの組み合わせは存在するかという問題。
入力が与えられたら、多項式時間で正しいか否かを判定できるので、 NP に含まれる問題。
これが NP-hard であることは、 全てのNPに属する問題が論理式で表されることにより証明された。
2SAT
2SAT は Np-hard ではない
3SAT
$(a+b+c)(d+e+f)$ のように、 ( ) の中が3つの項からなる論理式。
3SAT は NP-hard.
3SAT は SAT に帰着(reduce)可能。
Clique (最大クリーク問題)
クリークとは、グラフの一形態で、任意の2頂点の間に枝がある頂点の集合です。
問題としての Clique は、 あるグラフの中にある最大のクリークを見つける問題です。
- NP-hard
- Clique
- NP-complete
- 3SAT