FLYING

/* TODO: 気の利いた説明を書く */

多項式時間と指数時間

つまり、多項式時間=n^c, 指数時間=c^n(cは定数)。式だけを見れば似ているようにも思えるが、両者の違いは歴然としている。nが十分に小さければ指数時間のアルゴリズムのほうが早いこともあるが、nが大きくなるにつれ指数時間のアルゴリズムを解くのにかかる時間は「爆発」的に増大し、多項式時間とは比べ物にならないほどの時間を要する。必要な時間を計算してみると、数百億年とか余裕で出てくる。億年なんて最近は小学生だって言わねえよ。

この手の話は「計算複雑性理論」と呼ばれ、難しい問題を多項式時間で解く方法や、それぞれの問題を計算の困難さごとにクラス分けする方法が研究されている。計算の難しさを示すクラスの中で有名なものにNPとPがある。クラスPは多項式時間で解くことのできる問題を指し、クラスNPに含まれる。クラスNPはある答えを与えられたとき、その答えが正しいかどうかを多項式時間で検算できる問題を指す。

クラスNPの中でも、クラスNPに属する任意の問題Aから多項式時間で帰着可能な問題BをNP困難であるという。また、この問題B自身がNPクラスに属するならば、NP完全であるという。

あるNP問題Aは任意のNP問題Bに帰着できるから、1つのNP問題を多項式時間で解ける(解けない)ことが証明されれば、すべてのNP問題が多項式時間で解ける(解けない)ことが証明できる。クラスPとクラスNPが等しくないという予想(つまりクラスNPの問題は多項式時間では解けないという予想)は「P≠NP予想」と呼ばれ、計算複雑性理論における重要な問題のひとつであり、未だ証明されていない。