非決定性の学び方 - わさっきhb

クラスPとは、決定性チューリング機械において、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠（Witnessという）が与えられたとき、多項式時間でWitnessの正当性の判定（これを検証という）が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだ無いが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。
P≠NP予想 - Wikipedia

間違いではないけれど，NPの説明に，もどかしさを覚えます．「Yesとなる証拠（Witnessという）」という概念がなぜ出現するのか，なぜNPという名称になっているか，です．
キーワードは，wikipedia:非決定性チューリングマシンです．これを理解すれば，『クラスNPとは、非決定性チューリング機械において、多項式時間で判定可能な問題のクラス』と書くことができます．
また，Witnessというのは，「非決定性の振る舞いにより推測された答え」と表現することができます．ただし，推測するだけではダメとなっており，その推測された答えが正しいのを示すこと（＝Witnessの正当性の判定）は，構成される非決定性チューリングマシンの責務となっています．その際には，決定性の振る舞いで構成するほうが分りやすいし，それで十分です．
ここから，非決定性チューリングマシンの「定義」と「使い方」の違いを知ることができます．すなわち，非決定性チューリングマシンの形式的定義としては，あらゆる時点で非決定性の振る舞いをしてよいとなっていますが，ある問題がNPに属しているかを検討する際には，「非決定性の振る舞いにより答えを推測」と「決定性の振る舞いにより答えの正しさを検証」という2段構えで構成すればよく，全体として非決定性チューリングマシンとなりますし，それぞれが多項式時間で処理できるのなら，全体も多項式時間（したがってその問題はNPに属していると言える）になります．
その際，「非決定性の振る舞いにより答えを推測」が多項式時間を超えると話になりませんので，確認しておきますと，これは，推測する答えを書き出す時間となります．例えば，整数Nが与えられてその素因数の一つを求めなさいという素因数分解問題が与えられた場合*1，最も小さなNの素因数を（形式的な定義に基づくなら，テープに）書き出すだけです．Nの表現よりも小さなサイズであり，どう大きく見積もっても，Nの記述長に比例する時間で済みます．推測する答えの長さが，問題のサイズに対して多項式で表せない（例えば，指数領域になる）ような嫌らしい問題が来ると困りますが，P≠NPを考えるときには，そういう問題は無視して差し支えありません．
以上，『Yesとなる証拠（Witnessという）が与えられたとき、多項式時間でWitnessの正当性の判定（これを検証という）が可能な問題』と『非決定性チューリング機械において、多項式時間で判定可能な問題』が同じことを言っているという確認でした．
Wikipedia:P≠NP予想を基点に，「非決定性（非決定的，non-deterministic）」に関心を持った人のための，ガイドを書いておきます．ここで良書を紹介できればいいのですが，手元にありませんので割愛します．

（決定性）チューリングマシンを大まかに理解します．
- 何が有限で，どこに有限の制約がないかを，押さえておきます．
- 「問題」「言語」「受理」という用語を（そのいくつかは，日常使うのと少し違うことと合わせて）学びます．
- この段階では，Wikipediaを中心としたWebの情報でかまいません．
非決定性チューリングマシンを大まかに理解します．
- 決定性チューリングマシンとの違いを理解します．
- 「模倣」という言葉を自習します．
- この段階では，大学の授業のpptファイルやpdfファイルをよく目にするかもしれません．
有限オートマトンを学びます．
- 非決定性有限オートマトンを理解します．
- 有限オートマトンにおける，非決定性と決定性での受理能力の等価性（非決定性有限オートマトンに対して，それと同じ言語を受理する決定性有限オートマトンを構成する方法）を理解します．
- そろそろ本を買いましょう．大学の授業のページで，教科書・参考書になっているのがおすすめです．
チューリングマシンに立ち返ります．
- 有限オートマトンに何を付け加えたら，チューリングマシンになるかを確認します．
- 非決定性チューリングマシンと決定性チューリングマシンについて，受理能力が等価であるかどうかを，理由（構成方法）を含めて学びます．
プッシュダウンオートマトンを学びます．
- 有限オートマトンに何を付け加えたら，プッシュダウンオートマトンになるかを確認します．
- 有限オートマトンでは受理できないが，プッシュダウンオートマトンなら受理できる言語というのがあるのを学びます．
- プッシュダウンオートマトンにも決定性と非決定性があることを知り，例えばhttp://ocw.kyushu-u.ac.jp/0005/0003/lecture/3_6/ppt001.htmlを見て「あ，そうだよね」と言えるまで関連知識を身につけます．
- この段階では，「本に目を通す」のでは不十分で，本の練習問題や章末問題を解いて，一つ一つ自分の頭を点検していることでしょう．

この段階まで行けば，形式言語理論や計算論に足を踏み入れたようなものです．非決定性を学ぶというのから離れますが，「言語・機械・文法の関係」「反復補題(pumping lemma)」「文脈依存言語，線形拘束オートマトン」「決定不能性の証明」「多項式時間還元可能性」についても学習し，「『できない』のはなぜか？やり方に原因があるのか？そもそも手を出してはいけない（利用可能などんなやり方でも解決できない，手に負えない）課題なのか？」といった形で，目の前の課題に取り組めるようになれば，私からは言うことがありません．
関連：

*1:受理問題として書くなら，整数Nと別に整数mを入力に与え，「Nに，m未満の素因数が存在するか」となります．