『COMPUTERS AND INTRACTABILITY』を読んで生まれた疑問を解決する

久しぶりに更新します。

最近『Computers and Intractability』という、NP完全問題に関する本を読んでいました。

いくつか分からない単語とかがあり、それらを一応？解決したので覚書として記録します。多項式階層以下が分からなかった感じですが、復習としてクラスPやNP、NP完全についても触れておきます。

決定性Turing機械で、多項式時間で解ける(yesかnoかの判別がつく)問題のクラス。

計算量の関数yが、入力xに関して、y=xとか、y=x^2、y=logxとかの式で表せる。

偶数の判定とかはクラスPに属する。

決定性Turing機械で、答えが与えられたときに、その答えが正しいかどうかが多項式時間で判別できる問題のクラス。

問題を解くこと自体は、指数時間掛かってもいい。例えば計算量の関数が、y=2^xとかになってもいい。

以下の二つの条件を満たす問題。

1だけ満たすときは、NP困難という。NP困難問題はクラスNPに属していないので、yesかnoかの判定問題ではない。

あるNP完全問題は他の任意のNP完全問題に言い換えることができる。

例としては、巡回セールスマン問題、ハミルトン閉路など。

ここからがよく分からなくて調べたところ。間違ってたら教えてください。

A^Bを、クラスAのTuring機械にクラスBの何らかの問題を解くオラクルを付加して、強化したもので解ける決定問題の集合とする。例えば、P^NPは、NPを解くオラクルを備えることで、多項式時間で解ける問題のクラス。

P＝NPが証明されると、これらのクラスもすべてイコールになる。

日本語で書かれたものが少なく、苦労した部分です。

NPにおけるある決定問題について、オラクルを持つ決定性Turing機械によって多項式で解けるもの。つまり、P^NP？

これ、NP完全と何が違うのか全く分かりません……。一つのNP完全問題がNP-easyとなるなら帰着できるのですべてNP-easyとなるのでは？

そういう感じだからほとんど本で見かけないのかもしれないですね。

ちなみにNP-easyとNP-hard(NP困難)を同時に満たす問題は、NP-equivalentというそうです。例としては巡回セールスマン問題が挙げられていました。

計算時間が、入力に必要なビット長ではなく、入力の数値の多項式時間で表されるアルゴリズムのこと。

一般的に、計算時間の関数の入力は、Turing機械におけるステップ数などです。しかし、ステップ数的には多項式時間でも、入力に必要なビット長で関数を表すと、指数時間になる場合もあります。

例えば、ステップ数で表すと、O(n^4)であっても、ビット長で表すとO(2^4x)となるアルゴリズムとか。領域関係の計算クラス(DLとかPSPACEとか)もあるけど、あれは計算全体を指すので入力だけに着目すると疑似多項式時間アルゴリズムに属するようです。

計算時間の関数を、入力のビット長でなく、入力の数値で表しても指数関数となるもの。おそらくクラスNPに属する問題は、入力が何であれ、答えの正しさは多項式時間で求めることができるけど、解くこと自体は多項式で表せないのだと思います。(P=NPが証明されない限り)

NP完全性に強力かどうかがあるのは違和感があるんですけど……。同じNP完全同士であれば帰着可能な時点でNP完全問題に差はないのだと思っていたのですが違うのでしょうか。

とりあえず分からない単語はできるところまで調べてまとめてみました。タイトルで解決するとか言っておきながら疑問が生まれ続けてますけど。

もう少し英語が得意になって再チャレンジするか、辛抱強く追いかけて分かったことがあったら追記したいと思います。

情報系学生のお勉強覚書