[解決済み】"P=NP? "って何？なぜそんなに有名な質問なの？[クローズド］

質問

P=NPかどうかという問題は、おそらくコンピュータ・サイエンスの中で最も有名な問題である。これは何を意味するのだろうか？そして、なぜそんなに面白いのでしょうか？

あと、この文の真偽を証明する文章を投稿してください（追加単位）。

解答方法は？

Pは多項式時間を表します。 NPは非決定性多項式時間です。

定義

• 多項式時間 ここで n はデータのサイズ (例: ソートされるリストの要素数)、k は定数です。

• 複雑さ は、データ項目の数の関数として、かかる操作の数で測った時間である。

• 操作方法 は、特定のタスクの基本操作として理にかなったものであれば何でもよい。 ソートの場合、基本操作は比較である。 行列の乗算では、2つの数値の乗算が基本操作となる。

さて、問題は、決定論的と非決定論的とはどういうことなのか、ということです。 抽象的な計算モデルとして、チューリングマシン（TM）と呼ばれる架空のコンピュータがある。 この機械は有限個の状態と、有限個の記号を書き込んだり読み込んだりできる不連続のセルを持つ無限個のテープを持っている。 チューリング機械は、あるとき、いずれかの状態にあり、テープ上の特定のセルを見ている。 そのセルから何を読み取るかによって、そのセルに新しい記号を書き込んだり、テープを1セル進めたり戻したりして、別の状態に移行することができる。 これを状態遷移という。 驚くべきことに、状態と遷移を注意深く構成することによって、TMを設計することができ、それは、あらゆるコンピュータのプログラムを書くことに等しい。 このため、コンピュータにできること、できないことを証明するための理論モデルとして利用されている。

ここで気になるのは、TMには決定論的なものと非決定論的なものの2種類があることです。 決定論的論理回路は、テープから読み出す記号の数だけ状態遷移がある。 非決定論的 TM はこのような遷移を複数持つことができる、つまり同時に複数の 可能性をチェックすることができる。 これは、複数のスレッドを生成するようなものである。 しかし、実際のコンピュータでは、一度に実行できるスレッドの数は決まっている（CPUの数に等しい）。 現実のコンピュータは、基本的に有限のテープを持つ決定論的なTMである。 一方、非決定論的なTMは、量子コンピュータを除いて、物理的に実現することはできない。

非決定論的TMで解ける問題は、決定論的TMで解けることが証明されている。 しかし、どの程度の時間がかかるかは不明である。P=NP というのは、ある問題が非決定論的手法で多項式時間かかるなら、 同じ問題を多項式時間で解く決定論的手法を作ることができる、という意味である。 これまでのところ、それが可能であることを示すことができた人はいないが、不可能であることを示すことができた人もいない。

NP完全問題とは、NP問題Xのうち、任意のNP問題Yが多項式還元によってXに還元できるような問題を指します。 このことは、もし誰かがNP完全問題に対する多項式時間解法を考え出したら、それはあらゆるNP問題に対する多項式時間解法をも与えることを意味します。したがって、それはP=NPを証明することになる。逆に、もし誰かがP!=NPであることを証明したら、従来のコンピュータでNP問題を多項式時間で解く方法はないと確信することになるのです。

NP完全問題の例として、n個の変数を含むブール式が真となるような真理値の割り当てを求める問題がある。

今のところ、実際には、非決定論的なTMで多項式時間がかかる問題は、決定論的なTMや通常のコンピュータでは指数時間でしか処理できないのです。

例えば、真理値代入問題を解くには、2^nの可能性を試すしかない。