グラフの三色塗り分け問題の複雑性

n個の頂点を持つグラフが3色で塗り分けられるかという問題は、代表的なNP-完全問題である。n個の頂点が3色に塗られたグラフは、\(3^n\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、容易ではない。この問題への答えが「YES」であることを示すこと、すなわち、このグラフが3色の塗り分けを持つことを「証明」するのは「むずかしい」。

ただ、その「証明」は、「これがこのグラフの3色の塗り分けだ」という形をしているはずである。こうした「証明」が与えられた時、その「証明」が「正しい」か否かの「検証」は、n個の頂点が「塗り分け」の条件を満たしているかのチェックで、多項式時間で可能である。その「検証」は、元のNP問題より「やさしい」問題で、多項式時間のクラスPに属する。

こうした、PとNPの関係を拡張して、次のようなクラスを考えることができる。
\(2^n\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考える。\(2^n\)個の頂点が3色に塗られたグラフは、\(3^{2^n}\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、もちろん容易ではない。この問題の複雑性クラスをNEXPと呼ぶ。

なぜ、NEXP（それは"N+EXP"だ）という名前がつくかは、次のように考えればいい。この問題が「YES」という解を持つなら、「これがこのグラフの3色の塗り分けだ」という「証明」を持つ。この「証明」が正しいことの「検証」は、\(2^n\)個の頂点を一つづつ調べて、それが「塗り分け」の条件を満たしているかチェックすればいい。

それは、\(3^{2^n}\)個のグラフを検索することの「むずかしさ」とくらべれば、\(2^n\)個の頂点のチェックは、はるかに「やさしい」ことだ。この「検証」の複雑性は、\(2^n\) すなわち、EXP(指数関数的時間の複雑性)に属することになる。

もちろん、EXPクラスは、けっして「やさしい」クラスではない。それは、PやNPよりもずっと複雑なクラスである。それにもかかわらず、NEXPクラスの「むずかしさ」と比べると、EXPクラスはずっと「やさしい」クラスなのだ。

同様に、\(2^{2^n}\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考え、その複雑性NEEXPを考えることができる。このクラスは、その「証明」が与えられた時、それが「正しい」ことの「検証」が、\(2^{2^n}\)の複雑性 EEXPで可能なクラスである。

ここでも、証明の複雑性NEEXPは「むずかしい」のだが、その検証のクラスEEXPは、それと比べると「やさしい」ことになる。

こうした PとNPの関係の拡張は、もっと先に進めることができる。それについては、次回に取り上げることにしよう。