P≠NP予想

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/09 14:32 UTC 版)

概要

クラスPとは、決定性チューリングマシンにおいて、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠（Witnessという）が与えられたとき、多項式時間でWitnessの正当性の判定（これを検証という）が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだないが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。

仮にP＝NPであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかないさまざまな分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。NP問題は数千種類が知られているが、P＝NPが示された途端にそれらが全て多項式時間で解けるとは俄かに信じ難いことである。更に、P≠NPだと仮定して、何らかのNP完全問題の入力nビットについての既知の最良の計算量がO(kⁿ・poly(n,))であるようなときに、せめて基底のkを改善しよう（例えばk=2を1.9や1.8等に）という試みでさえ、ある程度進展した後に行き詰ることが経験的に知られている。これらの観察がP≠NP予想の重要な根拠の一つとなっている。

一方、P＝NPと予想する研究者も皆無ではない。ドナルド・クヌースはその一人であり、次のような論拠を挙げている^[1]。

P≠NPを証明する試みはことごとく失敗している（後述の#歴史参照）
NP問題をn^Mステップで解くアルゴリズムがあるとする。このMは例えば10↑↑↑↑3のような有限ながらも巨大な値を取れる。するとnビットの入力についてn^M個の論理演算や加算演算、シフト演算などを実施する途轍もない種類のアルゴリズムが考えられる訳で、これが全て失敗するとは信じ難い

但し彼は同時に次のようにも述べている。

「だが私が最も言いたいのは、たとえP＝NPが証明できたとしても、それが実用上役に立つとは思えないということだ。何故ならそうした証明はまず間違いなく非構成的だろうからだ。Mは存在すると思うが、人類がその値を知ることは決してないだろうとも思う。それどころかMの上界を求めることすら出来ないのではないか」^[1]

彼は存在が証明されているが実装は現実的に不可能と考えられているアルゴリズムを例として複数列挙している。

脚注