NP完全問題の困難さ
背景
トランザクション理論の学習をしていて、「あるトランザクションスケジューリングが与えられた時に、それがView Serializableを満たすかを否かを明らかにするのは、NP完全問題」という一文が出てきて、そもそもNP完全問題って何だっけ？どれほど難しい問題なんだっけ？となったので、P, NP, NP困難, NP完全の難しさについて学習（というか復習）しました。
知っておくべき事
まず、このページにとても良くまとまっているので、ここを見てください、と言えばそれで終わりなきがします。
ただ、それでは突然「○○はNP完全だよね」と言われて、即座にその真意をつかむのは難しいかと思いますので、以下の事を知っておくと良いでしょう。
計算の困難さ
P、NP、NP完全、NP困難の順で計算の複雑度が高まる。
ここでいう"複雑さ"や"困難"とは、計算機がある処理を行う際に、効率的な(処理時間が短くなる)アルゴリズムが存在するか、存在するならどのくらい効率的なアルゴリズムが存在するか、ということです。
具体例としては、探索問題とかを思い浮かべると良いでしょう。大量の数(n個)の列があったときに、ある数字が何番目に出てくるか、と言われたときに、その何億個の数字を先頭から見ていけば、答えは分かりますが、このしらみつぶし的な方法は効率が悪いです。これは線形探索と呼ばれ、今回のケースではO(n)です。
もし数列が、昇順に並んでいるとしたら、二分探索という方法があり、線形探索より計算量が小さいO(log2(n))で答えを発見できます。
このnが増えたとき、計算量が線形的に増える場合、数学的には、前者を多項式時間に解ける、と言い、計算としては困難ではないと言われます。
それに対し厄介なのは、nが増えたときに処理量（処理時間）がn乗で増えていくケースです。そういった問題は、ある程度規模の大きい入力値では、あまりに計算に時間がかかり、事実上計算不可能です。
ですので、問題が与えられたときに、多項式時間で解くアルゴリズムを見つけることが重要になってくるわけです。
このアルゴリズムが見つかりにくそうな問題ほど"困難"だと言われるわけです。
では、P、NP、NP完全、NP困難が、それぞれ、どのくらい困難な問題なのかを知っておきましょう。
P
Pの定義は、「判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるもの」です。
つまり、そもそも問題が、存在する/しない、Yes/No、などの二択問題に限られており、さらにその中で、ある入力値が与えられたら必ず一意の出力値を出す機械で、多項式時間に解けるもの、を指します。
ある入力値が与えられたら必ず一意の出力値を出す機械、は決定性チューリング機械と呼ばれますが、一般的な世の中のパソコンと同じ、と思えば結構です。
NP
NPの定義は、「非決定性チューリングマシンによって多項式時間で解くことができる問題」かつ、「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題」です。
ここから一気に難しくなったイメージですが、分かりやすく理解するために、問題を計算している途中の 状態 という概念を導入させてください。
決定性チューリングマシンは、計算途中のある状態から、少し計算を進めると、必ずある一意の状態になります。 しかし、非決定性チューリングマシンは、そうではありません。
例えば、計算を最後まで進めると最終的に計算終了になるが、そこに至る過程が複数あるという場合に、"次の状態"として、その複数の過程上の複数の状態のどれかが選択されるのであれば、それは非決定性チューリングマシンといえます。 また、イメージしにくいかもしれませんが、同時に複数の状態を持って、同時に様々な計算過程を進めていく事が出来る機械があれば、それも非決定性チューリングマシンです。量子コンピュータのようなイメージを持つと良いでしょう（ただし、実際は量子コンピュータ≠非決定性チューリングマシンです）。
要するに、「非決定性チューリングマシンによって多項式時間で解くことができる問題」は、「我々が一般的に利用する決定性チューリングマシンのコンピュータでは多項式時間で解けるか分からないけど、非決定性チューリングマシンでなら多項式時間で解ける問題」となるので、この時点でPよりもNPが難しそうです。
さらに、NPは、「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題」であり、もう少し分かりやすく言うと、「まー、仕方ないから、yesだって答えは分かったとして、それが正しいかどうかだけでも、多項式時間で判定出来る問題」といった所です。 Pは、「答えが正しいかどうかどころか、そもそも答えを導くことも含めて多項式時間で判定出来る」と言っているので、Pの方がNPよりも、簡単な問題を扱っていると言えます。
NP困難
NP困難の定義は、「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」です。 もう定義の時点で（というか名前の時点で）、NPより困難と言っています。
ただ、もう少し正確にいうと、問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義されます。 この帰着という言葉の意味するところが、実は定義が定まっていないそうなのですが、大まかに言うと、「あるNP困難問題を多項式時間で解ける機械がもしあれば、それを利用してどんなNPの問題も多項式時間で解くことができる」という事を指します。 最強感があります。
NP困難は、NPである必要もなければ、判定問題である必要もありません。
巡回セールスマン問題（セールスマンが複数の客先を最短距離で回る経路を導く）や、ナップサック問題（価値や大きさが異なる品物があり、それを最も価値が高くなるようにナップサックに詰め込む時の入れる品物の組み合わせ）がこれに当たります。 当然ながら、これらを多項式時間で解く方法は見つかっていません。
NP完全
NP完全の定義は、「クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである」。
多項式時間還元を解説すると、Aという問題とBという問題があり、Aと解くアルゴリズムをうまく使ってBも解けるなら、BはAに多項式時間還元可能（帰着可能）、ということです。 つまり、Aを解くアルゴリズムさえ見つかれば、Bが解けるわけです。 何となくそのAを解くと言うことは、相当難しいこと（少なくともBを解くよりは）のように思えます。 それを、NP完全は、NPに属する任意の問題から多項式還元可能と言っているので、「これさえ解けたらありとあらゆるNP問題が解ける、といえる問題」、と言うことになります。 明らかにNP界最強です。
しかし、NP困難は、あらゆるNPよりも同等以上に難しく、NP完全はNPに含まれる訳なので、NP完全よりもNP困難の方が難しいことになります。
NP完全問題が解けたと言ってもNP困難問題には関係ありませんが、NP困難な問題がとけたら、NP完全問題が解けることになります。
おわりに
最初の背景に戻ると、トランザクションのスケジュールがView Serializableの条件を満たすかどうかは、確かに判定問題です。 それ以上として、なぜこれがNP完全といえるのか、までは、証明を読んでいないですし、読んでも理解出来る自信がありません。 ただ、これが、P=NPと証明されるまでは（P≠NPと予想されています）、我々が利用するコンピュータでは多項式時間で解けるとは言えない問題、となります。
