computer-science - "P=NP?" とは何ですか? なぜこれほど有名な質問なのですか?

Question

P=NP かどうかという問題は、おそらくすべてのコンピューター サイエンスで最も有名です。どういう意味ですか？そして、なぜそれはとても興味深いのですか？

ああ、そして追加の信用のために、声明の真実または虚偽の証拠を投稿してください. :)

Answer 1

P は多項式時間を表します。NP は、非決定論的多項式時間の略です。

定義:

• 多項式時間とは、アルゴリズムの複雑さが O(n^k) であることを意味します。ここで、n はデータのサイズ (たとえば、並べ替えられるリスト内の要素の数) であり、k は定数です。

• 複雑度は、データ項目の数の関数として、必要な操作の数で測定される時間です。

• 操作は、特定のタスクの基本的な操作として意味のあるものです。並べ替えの場合、基本的な操作は比較です。行列の乗算では、基本演算は 2 つの数値の乗算です。

ここで問題は、決定論的対非決定論的とはどういう意味ですか? 抽象的な計算モデル、チューリング マシン (TM) と呼ばれる架空のコンピューターがあります。このマシンには有限数の状態と無限のテープがあり、有限のシンボル セットを読み書きできる個別のセルがあります。TM は常にいずれかの状態にあり、テープ上の特定のセルを調べています。そのセルから読み取る内容に応じて、新しいシンボルをそのセルに書き込み、テープを 1 セル前後に移動し、別の状態に移行できます。これを状態遷移と呼びます。驚くべきことに、状態と遷移を慎重に構築することで、TM を設計できます。これは、記述可能なコンピューター プログラムと同等です。

ここで関係する TM には、決定論的および非決定論的な 2 種類があります。決定論的 TM では、テープから読み取っているシンボルごとに、各状態からの遷移が 1 つだけあります。非決定論的 TM には、このような遷移が複数ある場合があります。つまり、複数の可能性を同時にチェックできます。これは、複数のスレッドを生成するようなものです。違いは、非決定論的 TM は必要な数の「スレッド」を生成できるのに対し、実際のコンピューターでは一度に特定の数のスレッドしか実行できない (CPU の数に等しい) ことです。実際には、コンピューターは基本的に有限のテープを使用した決定論的 TM です。一方、非決定論的 TM は、おそらく量子コンピューターを使用しない限り、物理的に実現できません。

非決定論的 TM で解決できる問題は、決定論的 TM で解決できることが証明されています。ただし、どのくらいの時間がかかるかは明確ではありません。ステートメント P=NP は、問題が非決定論的 TM で多項式時間を取る場合、同じ問題を多項式時間でも解決する決定論的 TM を構築できることを意味します。これまでのところ、それが可能であることを証明できた人は誰もいませんが、それが不可能であることも誰も証明できていません。

NP 完全問題とは、任意の NP 問題 Y を多項式簡約によって X に簡約できるような NP 問題 X を意味します。これは、誰かが NP 完全問題の多項式時間解を思いついた場合、NP 問題の多項式時間解も与えることを意味します。したがって、P=NP が証明されます。逆に、誰かが P!=NP であることを証明した場合、従来のコンピューターでは多項式時間で NP 問題を解く方法がないと確信できます。

NP 完全問題の例は、n 個の変数を含むブール式を真にする真偽代入を見つける問題です。
現時点では、非決定論的 TM で多項式時間を要する問題は、決定論的 TM または従来のコンピュータでは指数時間でしか実行できません。
たとえば、真理割り当て問題を解決する唯一の方法は、2^n の可能性を試すことです。

Answer 2

1. 答えが多項式時間で計算できる場合、はいまたはいいえの問題はP ( P多項式時間) にあります。
2. イエスの答えが多項式時間で検証できる場合、イエスかノーの問題はNP ( N on-決定論的多項式時間) にあります。

直観的に、問題がPにある場合、それはNPにあることがわかります。Pの問題に対する潜在的な答えが与えられると、答えを再計算するだけで答えを検証できます。

NPのすべての問題がPにあるかどうかは、あまり明白ではなく、答えるのがはるかに困難です。多項式時間で答えを検証できるということは、その答えを多項式時間で計算できるということですか?

NP完全であることが知られている重要な問題が多数あります(基本的に、これらの問題が P にあると証明された場合、すべての NP問題はPにあることが証明されます)。P = NPの場合、これらの問題はすべて効率的な (多項式時間) 解を持つことが証明されます。

ほとんどの科学者は、P != NPであると信じています。ただし、 P = NP またはP != NPの証明はまだ確立されていません。誰かがいずれかの予想を証明した場合、100 万米ドルを獲得できます。

Answer 3

私が考えることができる最も簡単な答えを与えるために：

特定の数の入力を取り、さまざまな潜在的な解決策がある問題があるとします。これにより、特定の入力の問題が解決される場合とされない場合があります。パズル雑誌のロジックパズルが良い例です。入力は条件（「ジョージは青または緑の家に住んでいない」）であり、考えられる解決策はステートメントのリストです（「ジョージは黄色に住んでいます」）。家、エンドウ豆を育て、犬を飼っている」）。有名な例は巡回セールスマン問題です。都市のリスト、任意の都市から他の都市に移動する時間、および時間制限が与えられた場合、考えられる解決策は、セールスマンが訪問した順序の都市のリストです。移動時間の合計が制限時間よりも短い場合は機能します。

このような問題は、潜在的な解決策を効率的にチェックして、それが機能するかどうかを確認できれば、NPにあります。たとえば、セールスマンが順番に訪問する都市のリストを指定すると、都市間の各旅行の時間を合計して、制限時間内にあるかどうかを簡単に確認できます。解決策が存在する場合、それを効率的に見つけることができれば、問題はPにあります。

（ここでは、効率的に、正確な数学的意味があります。実際には、大きな問題を解決するのが不当に難しくないことを意味します。考えられる解決策を探すとき、非効率的な方法は、考えられるすべての解決策、またはそれに近いものをリストすることです。 、効率的な方法では、はるかに限定されたセットを検索する必要があります。）

したがって、P = NP問題は次のように表すことができます。上記の種類の問題の解決策を効率的に検証できる場合、解決策を効率的に見つける（または解決策がないことを証明する）ことができますか？明白な答えは「なぜあなたはできるべきなのか」であり、それが今日の問題のほとんどです。誰もそれを何らかの方法で証明することができませんでした、そしてそれは多くの数学者とコンピュータ科学者を悩ませます。そのため、解決策を証明できる人は誰でも、ClaypoolFoundationから100万ドルの資金を調達できます。

一般に、PはNPと等しくなく、解を見つける一般的な方法はないと想定しています。P = NPであることが判明した場合、多くのことが変化します。たとえば、暗号化は不可能になり、それによってインターネット上でのあらゆる種類のプライバシーや検証可能性が実現します。結局のところ、暗号化されたテキストとキーを効率的に取得して元のテキストを生成できるため、P = NPの場合、事前に知らなくてもキーを効率的に見つけることができます。パスワードクラッキングは些細なことになるでしょう。一方で、効果的に解決できる計画問題と資源配分問題のクラス全体があります。

NP完全の説明を聞いたことがあるかもしれません。NP完全問題は（もちろん）NPであり、この興味深い特性を持っています。それがPにある場合、すべてのNP問題はそうであるため、P=NPです。巡回セールスマン問題やパズル雑誌のロジックパズルを効率的に解決する方法を見つけることができれば、NPのあらゆるものを効率的に解決できます。NP完全問題は、ある意味で最も難しい種類のNP問題です。

したがって、NP完全問題の効率的な一般的な解決手法を見つけることができる場合、またはそのような問題が存在しないことを証明できる場合は、名声と幸運があなたのものになります。

Answer 4

私の謙虚な知識からの短い要約：

いくつかの簡単な計算問題 (グラフ内の 2 点間の最短経路を見つけるなど) があり、かなり高速に計算できます (O(n^k)、n は入力のサイズ、k は定数です (グラフの場合は、頂点または辺の数です))。

グラフのすべての頂点を横切るパスを見つけたり、公開鍵から RSA 秘密鍵を取得したりするのが難しい (O(e^n)) など、その他の問題もあります。

しかし CS は、問題は、非決定論的なチューリング マシンを決定論的なチューリング マシンに「変換」できないことですが、非決定論的な有限オートマトン (正規表現パーサーなど) を決定論的なオートマトン (まあ、あなたはできますが、マシンの実行時間は長くなります)。つまり、考えられるすべてのパスを試す必要があります (通常、賢い CS 教授はいくつかのパスを除外できます)。

興味深いのは、誰も解決策をまったく考えていないからです。本当だと言う人もいれば、嘘だと言う人もいますが、コンセンサスはありません。もう 1 つの興味深い点は、ソリューションが公開/秘密キー暗号化 (RSA など) にとって有害で​​あるということです。RSA キーの生成が現在行われているのと同じくらい簡単に、それらを破ることができます。

そして、それはかなり刺激的な問題です。

Answer 5

質問の P=?NP 部分の何とその理由に追加できることはあまりありませんが、証明に関しては. 証拠は、いくらかの信用に値するだけでなく、ミレニアム問題の 1 つを解決します。興味深い世論調査が最近実施され、公開された結果 (PDF)は、証明の主題に関して間違いなく読む価値があります。

Answer 6

まず、いくつかの定義：

• n^kあるものよりも短い時間で解を計算できる場合、特定の問題はPにあります。kここnで、は入力のサイズです。たとえば、n log n未満でソートを実行できるn^2ため、ソートは多項式時間です。

• 問題は、最大で時間内に検証できるk最大サイズの解が存在するようなものが存在する場合、NPにあります。グラフの3色を使用します。グラフが与えられた場合、3色はサイズのある（頂点、色）ペアのリストであり、すべての隣接する色が異なる色であるかどうかを時間内に（または）確認できます。したがって、グラフは、短くて簡単に検証できる解決策がある場合にのみ3色になります。n^kn^kO(n)O(m)O(n^2)

NPの同等の定義は、「ポリノミアル時間で非決定論的チューリングマシンによって解決可能な問題」です。それは名前の由来を教えてくれますが、NP問題がどのようなものであるかを直感的に感じることはできません。

PはNPのサブセットであることに注意してください。多項式時間で解を見つけることができる場合、多項式時間で検証できる解があります。与えられた解が見つけられる解と等しいことを確認してください。

なぜ質問はP =? NP面白いのですか？これに答えるには、まずNP完全問題とは何かを確認する必要があります。簡単に言えば、

• 問題Lは、（1）LがPにあり、（2）Lを解くアルゴリズムを使用して、NPの問題L'を解くことができる場合にNP完全です。つまり、L'のインスタンスが与えられた場合、L'のインスタンスに解がある場合にのみ、解を持つLのインスタンスを作成できます。正式に言えば、NPのすべての問題L'はLに還元できます。

Lのインスタンスは、多項式時間で計算可能であり、L'のサイズの多項式サイズを持っている必要があることに注意してください。このようにして、多項式時間でNP完全問題を解くと、すべてのNP問題に対する多項式時間解が得られます。

次に例を示します。グラフの3色がNP困難な問題であることがわかっているとします。ブール式の充足可能性を決定することもNP困難な問題であることを証明したいと思います。

各頂点vに対して、2つのブール変数v_hとv_l、および要件（v_hまたはv_l）があります。各ペアは値{01、10、11}のみを持つことができ、色1、2、および3と考えることができます。

各エッジ（u、v）について、（u_h、u_l）！=（v_h、v_l）という要件があります。あれは、

not ((u_h and not u_l) and (v_h and not v_l) or ...) すべての等しい構成を列挙し、どちらも当てはまらないことを規定します。

ANDこれらすべての制約を一緒にすると、多項式サイズ（O(n+m)）を持つブール式が得られます。計算にも多項式時間がかかることを確認できますO(1)。頂点ごとおよびエッジごとに単純な処理を実行しています。

私が作成したブール式を解くことができれば、グラフ彩色も解くことができます。変数v_hとv_lの各ペアについて、vの色をそれらの変数の値に一致するものとします。式の構築により、隣人は同じ色になりません。

したがって、グラフの3色がNP完全である場合、ブール式の充足可能性も同様です。

グラフの3色はNP完全であることがわかっています。ただし、歴史的には、最初にブール回路の満足度のNP完全性を示し、次にそれを3色性に減らすことによって（その逆ではなく）、それを知るようになりました。