はじめに
内容の誤りがあるかもしれません。
誤りに気付かれた方はコメントで教えていただけると大変助かります。
わかったこと
- 「問題Aの入力を、決定性チューリングマシンで、かつ多項式時間で問題Bの入力に変換→問題Bを解く→その答えが問題Aの答えである」が、Aのすべての入力に対して成り立つ場合、「AがBに多項式時間多対一還元（帰着）可能」といい、$A\leq ^p_{m} B$と書く（表記ゆれあり）。
- 「チューリングマシンとは？」って人は、オートマトンや言語理論を学習してみてください。
- 問題Bは、問題Aに比べて、同等以上の難しさである（同等かも）
- 還元には、ほかにチューリング還元というのがあるが、今回は考えない。
- 「還元」についての詳しい説明は、こちらの記事を参照してください。
- $\leq ^p_{m}$は、その不等号っぽい形から想像がつくように、順序関係（前順序関係）である。つまり、
- $A\leq ^p_{m}A$が成り立つ（反射律）。
- $A\leq ^p_{m}B\land B\leq ^p_{m}C\Rightarrow A\leq ^p_{m}C$が成り立つ（推移律）。
- $A\leq ^p_{m} B$のとき、
- 問題BがPに属する（$B\in \textrm{P}$）なら、問題AもPに属する（$A\in \textrm{P}$）。
- $B\in \textrm{NP}$なら、$A\in \textrm{NP}$。
- $B\in \textrm{co-NP}$なら、$A\in \textrm{co-NP}$1。
- 上から抑え込むイメージ。
各クラスの説明
注意：ここで説明するクラスは、すべて決定問題（答えがYES/NOである問題）のクラスです。
DTIME
厳密には集合族。
$\textrm{DTIME}(f(n))$というクラス（集合）を、すべての$f(n)$について要素として持つ考えたときの集合。
$\textrm{DTIME}(f(n))$は、決定性チューリングマシンを用いて、$O(f(n))$の時間で解ける問題のクラス。
NTIME
これも集合族。
$\textrm{DTIME}$は決定性チューリングマシンを用いた定義だったが、$\textrm{NTIME}$は非決定性チューリングマシンを用いた定義。
$\textrm{NTIME}(f(n))$は、非決定性チューリングマシンを用いて、$O(f(n))$の時間で解ける問題のクラス。
また、同値な表現として、問題の答えがYESである例（証拠）が与えられたとき、それが本当に正しいのか、決定性チューリングマシンで、多項式時間で検証できる問題のクラスの族（詳しくは、NPの節で説明しています）。
P
決定性チューリングマシンによって、多項式時間で解かれる問題のクラス。
$\textrm{DTIME}$で定義すると、以下の通り。
\begin{equation*}
\textrm{P}=\bigcup_{k\in \mathbb{N}}\textrm{DTIME}(n^{k})
\end{equation*}
NP
非決定性チューリングマシンによって、多項式時間で解かれる問題のクラス。
$\textrm{NTIME}$で定義すると、以下の通り。
\begin{equation*}
\textrm{NP}=\bigcup_{k\in \mathbb{N}}\textrm{NTIME}(n^{k})
\end{equation*}
同値な表現として、問題の答えがYESである例（証拠）が与えられたとき、それが本当に正しいのか、決定性チューリングマシンで、多項式時間で検証できる問題のクラス。
例えば、充足可能性問題（SAT）2は、変数の真偽の組み合わせを証拠として実際に論理式に入力すると、
- 論理式全体が真→証拠は正しい
- 論理式全体が偽→証拠は誤り3
と、多項式時間で検証できるので、クラスNPに属する。
決定性チューリングマシンでは、NPに属するすべての問題が、多項式時間で解けないわけではない。
非決定性チューリングマシンの受理能力は、少なくとも決定性チューリングマシンの受理能力より低いことはないから、$\textrm{P}\subseteq \textrm{NP}$が成り立つ。
NP困難
任意のNP問題が帰着可能な問題のクラス。
問題Aと、任意のNP問題Bとの間に、$A\leq^p_{m} B$が成り立つような問題Aは、NP困難である。ということ。
「NP問題と同等か、それより難しい問題」と表現されることも。
NPに属する問題（下記の「NP完全問題」にあたる）と、NPに属さない（NPより真に難しい問題）に分けられる。
NP完全
NPかつNP困難な問題。
「NPの中で最も難しい問題たちのクラス」と表現されることも。
包含関係
- $\textrm{P}\subseteq \textrm{NP}$である。
- さっき説明した通り
- $\textrm{P}\supseteq \textrm{NP}$かどうかは未解決。
- $\textrm{P}=\textrm{NP}\Leftrightarrow \textrm{P}\supseteq \textrm{NP}$であり、$\textrm{P}\ne \textrm{NP}\Leftrightarrow \textrm{P}\nsupseteq \textrm{NP}$である。（集合の包含関係と1を合わせて考える）
- $\textrm{NP}$完全$\subseteq \textrm{NP}$である。
- NP完全の定義より明らか。
- $\textrm{NP}$完全$\supseteq \textrm{NP}$かどうかはわからんかった。
- $\textrm{P}\ne \textrm{NP}$なら、PにもNP完全にも属さないNP問題が存在する（このような問題が属するクラスをNP-intermediateと呼ぶらしい）ので、$\textrm{NP}$完全$\nsupseteq \textrm{NP}$。
- $\textrm{P}\ne \textrm{NP}$ならばNP-intermediateが空でないことを示す定理を、Ladnerの定理というらしい（これもさっきのリンクのWikipedia情報）。
- $\textrm{P}=\textrm{NP}$なら、当然NP-intermediateは空。$\textrm{NP}$完全$\supseteq \textrm{NP}$かどうかは調べてもわからなかったので、詳しい人教えてください。
- Wikipediaの「NP困難」記事の図には、$\textrm{P}=\textrm{NP}\simeq \textrm{NP}$完全っぽく書かれている（$\simeq$ ってなんだ？）
- $\textrm{P} \supseteq \textrm{NP}$完全であれば、証明できそうだが…
- $\textrm{P}\ne \textrm{NP}$なら、PにもNP完全にも属さないNP問題が存在する（このような問題が属するクラスをNP-intermediateと呼ぶらしい）ので、$\textrm{NP}$完全$\nsupseteq \textrm{NP}$。
- $\textrm{NP}$完全$\subseteq \textrm{NP}$困難である。
- NP完全である条件から、NPに属するという条件を除いたのがNP困難だから。
- $\textrm{NP}$完全$\nsupseteq \textrm{NP}$困難である。
- 停止性問題など、NP完全より難しいNP困難問題がある。
- 停止性問題がNP困難である証明は、これから。
- つまり、NPから多項式時間帰着可能な問題で、NPでない例が存在する。
- 任意のNP問題をA、停止性問題をBとすると、必ず$A\leq ^p_{m} B$が成り立つ。
最後に
4は多分未解決だと思いますが、本当に未解決なのかわからないのでぜひ教えてください。
コメント