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であることがいえる。

論理式が与えられた時に、その論理式を真にするようなリテラルの組み合わせは存在するかという問題。
入力が与えられたら、多項式時間で正しいか否かを判定できるので、 NP に含まれる問題。

これが NP-hard であることは、全てのNPに属する問題が論理式で表されることにより証明された。

2SAT は Np-hard ではない

$(a+b+c)(d+e+f)$ のように、 ( ) の中が3つの項からなる論理式。

3SAT は NP-hard.
3SAT は SAT に帰着(reduce)可能。

クリークとは、グラフの一形態で、任意の2頂点の間に枝がある頂点の集合です。
問題としての Clique は、あるグラフの中にある最大のクリークを見つける問題です。