[数理]第3回組合せ問題
2006年10月30日（月）18:30｜谷口
谷口です。
前回はオーダーという計算量の概念について書きました。 今回は問題のクラスという概念を紹介します。 この問題のクラスというのは解くための計算量によって分類されます。また、計算量が大きい問題ほど難しいと捉える慣わしになっています。
キーワード
- 多項式オーダー
- 指数オーダー
- P=NP?
おさらい
- 多項式オーダー:実行に要する時間が、入力に対して多項式的に増加する
- 指数オーダー:実行に要する時間が、入力に対して指数的に増加する
多項式とは、独立した変数の四則演算（＋－×÷）で表わされた式のことです。
例えば、次のようなデータベースがあるとします。
| table1 | table2 | |||
| column1 | column2 | column1 | column2 | |
| record1 | りんご | 100 | お茶 | 500 |
| record2 | みかん | 50 | コーヒー | 250 |
| record3 | ばなな | 100 | ジュース | 350 |
ここで、select * from table1 という要求をした場合、返ってくるレコードは3つです。
| column1 | column2 |
| りんご | 100 |
| みかん | 50 |
| ばなな | 100 |
１レコードを取得する時間が固定であるとすると、これはレコード数に比例した時間がかかることになります。（O(n)）
次に、select * from table1, table2 という要求をした場合、返ってくるレコードは9つです。
| table1.column1 | table1.column2 | table2.column1 | table2.column2 |
| りんご | 100 | お茶 | 500 |
| みかん | 50 | お茶 | 500 |
| ばなな | 100 | お茶 | 500 |
| りんご | 100 | コーヒー | 250 |
| みかん | 50 | コーヒー | 250 |
| ばなな | 100 | コーヒー | 250 |
| りんご | 100 | ジュース | 350 |
| みかん | 50 | ジュース | 350 |
| ばなな | 100 | ジュース | 350 |
これは、32。つまり、レコード数テーブル数となります。*1同様に1レコードを取得する時間が固定であるとすると、
仮に、結合に要するテーブル数が一定で、レコード数が可変だとすると、レコード数の多項式オーダーとなります。 仮に、レコード数が一定で、結合に要するテーブル数が可変だとすると、テーブル数の指数オーダーとなります。
※ここで挙げたのは、あくまで例です。実際にDBを運用する場合は、結合するテーブル数が可変になるようには設計しないでしょう。
*1：正確にはtable1のレコード数×table2のレコード数となりますが、説明のためこのような表現をしました。
問題のクラス
厳密には、決定性チューリングマシンやら非決定性チューリングマシンやら小難しいもので定義されますが、 ここでは、おおざっぱに書きます。
- P ：多項式時間で解が求められる決定問題のクラス
- NP :解の検証は多項式時間でできるが、解を求めるのはその限りではない問題群。代表的な問題：ハミルトン閉路問題など SATの場合ですと、 ある変数の値の組が渡されたとき、 ・式の数だけ成立可否を判定する。 成立可否の判定は式に含まれる変数の数だけ検証すればよいので、O(m×n)となる。 一方、解を求めるには、最悪すべての変数の組を検証しなければならないので、 O(m×2^n)となり、これは多項式オーダーとなりません。つまり、SATはNPに属します。
このようなクラス分けをする意義は、対象としている問題がどのクラスに属するかということで、ある程度解決方法が分かることが挙げられます。また逆に、各クラスで属している問題であれば、ある程度は今後の課題も共通しますので、研究する上では何をどうすることで貢献できるかがわかるのも利点です。 （次回以降に説明予定の 完全問題 と多項式時間帰着が絡んできます。）
また、この他にもPSPACE、NPSPACE、EXPTIMEといった問題のクラスがありますが、ここでは割愛させていただきます。
「P=NP?」命題
この命題は上記の問題のクラスPとNPの関係に対する問いかけです。厳密にいうと少し違いますが、クラスNPとクラスPに属する問題を解くための計算量のオーダーが同じであるかどうか？といった感じでしょうか。
少し踏み込むと、NPがPを含むのは自明（多項式時間で解が求められるので、NPの条件を満たすことが確実）なので、
P ⊆ NP
つまり、この命題は、
P ⊇ NP
が成り立つかどうかを問うているのと同義です。 もし、「P=NP」であれば、SATなどクラスNPに属する問題が多項式時間で解けるということになります。なお、この命題の真偽が証明できたら100万ドルもらえるそうです。
おわりに
次回は完全問題と困難問題についてお話できたらと思います。
