「やさしい問題」と「むずかしい問題」

　リソースによる複雑性の階層

先に、「複雑さ」を、ある問題を計算するのに必要な時間とメモリーの大きさで分類するというアプローチを紹介しました。

ある時間\(T_0\)では解けないけれど、\(T_0\) より大きな時間 \(T_1\)では解ける 問題、あるいは、ある量のメモリー空間\(S_0\)では解けないけれど、\(S_0\) より大きなメモリー空間 \(S_1\)では解ける 問題を考えて、多くの計算リソース（時間、空間）を要する問題を「複雑な問題」と考えることは自然なことです。また、多くの計算リソースを要する問題を「むずかしい問題」、より少ない計算リソースを要する問題を「やさしい問題」と考えることができます。

こうした「時間複雑性」や「空間複雑性」といった階層が存在することは、ある問題をできるだけ効率的に、短いステップで少ないメモリーで書こうとするプログラマーが、日常的に意識していることです。

一つの問題には、それを解く複数のアルゴリズムが存在しえますので、ある問題にとって、それを解くアルゴリズムの数だけ具体的な実行計算複雑性が存在することになります。例えば、n個のものを大きさ順に並べ替えるSORT問題の実行計算複雑性は、bubble sortのアルゴリズムなら \(O(n^2)\)に、quick sort のアルゴリズムなら\(O(n log n)\)になります。 

プログラマにとっての実践的な関心は、その下限を目指すことですが、下限を確定することは、理論的にも実践的にも簡単なことではありません。

　コルモゴロフの「複雑性」

複雑性については、今回のセミナーで扱うアプローチとは別の流儀があります。コルモゴロフは、ある対象の複雑性を「その対象を出力するプログラムの最小の大きさ」で定義します。これは、ある問題を解くアルゴリズムの実行計算複雑性の下限を追求するアプローチと、向いているベクトルはよく似ています。それをもっと抽象化・一般化したものです。

ある問題についての最小のプログラムを「エレガントなプログラム」と呼ぶことにすると、チャイティンは、「あるプログラムがエレガントであることを我々は証明できない」ことを証明しました。これを「チャイティンの不完全性定理」といいます。

これらについては、以前の僕のブログを参照ください。

　●「コルモゴロフの複雑性」
　　　https://maruyama097.blogspot.com/2017/01/blog-post.html
　●「チャイティンの不完全性定理」
　　　https://maruyama097.blogspot.com/2017/01/blog-post_8.html

　NPというコンセプト

現代の「複雑性理論」は、それらとも、アルゴリズムの複雑性の下限を求めるアプローチとも異なる道を選びます。歴史的には、現代の「複雑性理論」は、NPという複雑性のクラスと「NP-完全」という概念の発見によって始まります。

NPは、ある問題とその答えが与えられた時、その答えが「正しい」ことを多項式時間で「検証」できる時間複雑性のクラスです。（この定義の双対で、その答えが「間違っている」ことを多項式時間で「検証」できるクラスをcoNPと呼びます。）

先のSORT問題を NP問題として捉えると、その並べ替えが正しいことの検証は、n個のもの全てが順番に並んでいるかの n-1回のチェックで可能です。このn-1という値は下限です。最悪ケースを考えれば、これ以下にはできないことがわかります。それは、どのSORTアルゴリズムを採用するかには依存しません。

少しでも速いSORTアルゴリズムの開発に命をかけている人には、当たり前すぎてつまらないことのように思うかもしれませんが、n-1回のチェックで、ソートの正しさが検証できるというのは、ある意味、SORT問題の本質を捉えています。

前回見た「時間複雑性」や「空間複雑性」の階層では、「やさしい問題」と「むずかしい問題」の区別は、必要な計算リソース（時間、空間）の量的区別に帰着します。しかし、NPというクラスが複雑性の階層に持ち込むものは、それとは違っています。それは、ある問題に答えを与えることと、その答えを検証することとは違うものだという質的区別です。

ある問題に答えを与えるのは「むずかしい問題」だとしても、その答えが正しいかをチェックするのは、それよりも「やさしい問題」になります。数学の証明を行うのは一般に「むずかしい」のですが、その証明が正しいかを検証するのは、証明することと比べれば「やさしい」のです。

　「証明は「むずかしい」が検証は「やさしい」！」

このイメージはとても大事です。

もちろん、このことは、NP問題自身が、「やさしい問題」であることを意味しません。それは、その検証が「やさしい」ことを意味しているだけです。

NP問題というクラスは、とても豊かなものです。例えば、全ての数学的証明は、NP問題です。なぜなら、その証明が「正しい」ことを、我々が理解できるものでなければ、証明としての意味を持たないからです。それは、その証明の各ステップを、我々が有限の時間の中で後追いでチェックできるということを意味します。ここでは、我々人間にとって有限の時間とは、指数関数ではなく多項式で表される時間だと考えています。

PとNPの関係を一般化して、ある時間複雑性のクラス\({\bf T}\)に対して、その答えが正しいことの「検証」がクラスTに属する複雑性のクラス\({\bf NT}\)を考えることができます。例えば、\({\bf NEXP}\)というクラスは、このクラスに属する問題の答えが正しいことの検証が、\({\bf EXP}\)時間の複雑性で可能な複雑性のクラスのことです。

こうした拡張によって、複雑性のクラスは、先日の図で表した「時間複雑性」と「空間複雑性」の階層だけからものと比べて、少し豊かなものになります。こうして拡張された複雑性の世界を図にしてみました。是非、先日の図と比較してみてください。

この図について、補足しますと、\({\bf P}\)のことを「決定性チューリングマシン」で多項式時間で計算される時間複雑性のクラス\({\bf DTIME}(p(n))\)で表しましたが、\({\bf NP}\)は「非決定性チューリングマシン」で多項式時間で計算きれる時間複雑性のクラス \({\bf NTIME}(p(n)\)として表されます。