改めてP=NP？って

さて、これまで簡単に、TM、NTM、OTMなどから、計算量のクラスPとNPのことを説明してきました。ここでは、あらためてP=NPと言う関係は何を意味しているのか、ということを考えましょう。今回は何もおもしろい事は思いつかなかったのでその辺の期待はスルーでお願いします。

さて、普通に考えてクラスPにあたる問題とクラスNPにあたる問題と何らかの関係があるのは理解できます。どちらも、基本的には入力が違うだけで、それを解くためのTMの構造は同じでした。

それで、クラスNPの問題の中にクラスPの問題が入っているとしたら納得できます。NTMの適当な入力がクラスPの問題になっていればそれはそれで、多項式時間で解けるでしょうから。従って、普通に、

P⊆NP　（クラスPの問題はクラスNPの問題の部分集合である）

ということは誰もが納得できる話でしょう。

では、クラスNPの問題は最終的にクラスPの問題として考えて良いのか、言い方を変えればクラスPの問題へ変換できるのか。これがP=NP？問題のキモです。数学的にはクラスPはクラスNPの真部分集合になるかという言い方をします。

では、何らかの変換でクラスNPの問題がクラスPに変換されたとしましょう。でも、その変換に多項式時間ではなく前にも言ったO(5^n)のような指数関数時間がかかったりすれば、それはP⊆NPというだけでP=NPではありませんね。

というわけで、クラスNPという問題がどういう問題か、その核心は何か、と言うことを次からは話していきます。いわゆる一つのcookの定理のお話です。

でも、ちょっとだけ話しちゃおうかなぁ。

クラスNPの核心的な部分の問題をNP完全といいます。クラスNPの問題はNP完全な問題に置き換えられます。次からはそういう話です。

そうすれば、P=NP?の問題は、

　１．まず、クラスNPの問題が、多項式時間でNP完全な問題に置き換えられ、

　２．NP完全な問題とクラスPの問題が最終的には同じクラスに属するか、

ということに問題が分けられますよね。

そういうわけで、まず、クラスNPの問題が多項式時間以内でNP完全な問題に置き換えられることを示しましょう。そうするとクラスNPの問題は、NP完全な問題だけを扱えばいい、ということになるからです。

あと、もう一つ。いわゆる一つのワンモアシングです（分かる人には分かる、このギャグ）。この辺の問題でクラスNP以上の時間がかかりそうだというときにNP困難（NP-hard）な問題といいます。とっても時間がかかりそうな問題の時に、「この問題はNPハードな問題だ」とかいうとちょっとカッコよさげですよね（笑い）。でも、わたしも、NP完全とかNP困難とかよく間違えるので下手にカッコつけない方が身のためだと、一応ご忠告しておきます。