還元

非可解性の証明や、NP完全性の証明をするときには、
すでに非可解であったり、NP完全であると証明されている問題のインスタンスを
証明したい問題のインスタンスに還元することで証明をする。

これがなんとも分かりにくいので、
解きたい問題とインスタンスの関係に注目しながらそして流れイメージしながら考えてみる。
NPと非可解は手法的に似てるので、非可解性の方について示す。

• 解きたい問題

〜は非可解であることを示せ
問題＝TMのことであり、答えであるyes,noを出力する。(このTMをTM Tとする)
非可解とは解けない、停止しないということである。つまりyes,noの答えがでないことを示すのが目的。

• 証明する問題のインスタンス

その問題の入力。TM Tを関数と考えたときの引数と考えるとわかりやすい。
TMが入力であることも。インスタンスはあくまでも入力の一例であり、無限に存在するので、
それを一般化してまとめたものについて考える。これをTM Mとする。

• すでに証明された問題

〜は非可解である。　つまり停止しないので、yes,noは出力されない。　TM Sとする

• 証明済問題のインスタンス

同様に一般化されたものをTM Nとする。
例：ε停止問題ではTM NはNのうちのどれにεを入力したときでも停止しないインスタンスの集合

• 還元

この作業を行うTMをTM Rとする。
MからNへともれなく、写像する。

証明の大まかな流れとして、したいことは
背理法で仮定→還元の存在→矛盾
イメージするとこんな感じ。　○がインスタンスの集合、→が遷移を表す。
たとえば、RはNを入力して、Mを出力する。

• 背理法で仮定

問題は可解であると仮定、つまり停止するTの存在を仮定

• 還元

NからMへのある写像Rの存在を示す。（そうなるRを探す）　
ここで、RはM内の各インスタンスの正誤を保存したままNに写像する必要があり*1、またRは必ず停止する必要がある。

• 矛盾

Nが非可解であることは真であるが、仮定のTとRの存在から、NにRTの順にTMを実行するとyes,noがわかってしまう。
これは矛盾。　　よって示せた。

となる。
写像Rの存在を示せば、証明できるというのはこういうことである。

TM MとTM Nが分かりにくいのでさらに詳細に。
ε停止問題の非可解証明の場合。
TM N はTM停止問題のインスタンスであるTM nとその入力ρであり、
TM Mはε停止問題のインスタンスであるTM mである。(入力はεで固定)

この様にNのインスタンスがもれなく写像できていれば、還元できていることになるので、
もれなく写像できるようにRを作る。

以上！　ですが、これはおかしいやろ的な部分があれば、ご指摘ください！

*1:実は、可解と仮定しているので、正誤を全く逆に保存していてもよいらしい