高齢者P対NP問題
それでは、P対NP問題は何ですか？
記録のために、現状はP≤NPということです。
P（多項式時間）は、多項式時間でアルゴリズムによって解くことができる問題のクラスを指します。 Pクラスの問題は、乗算のような単純なものから、リスト内の最大数を見つけることまでの範囲です。 それらは比較的簡単な問題のセットです。NP（non-deterministic polynomial time）は、非決定論的なコンピュータによって多項式時間で解くことができる問題のクラスを指します。, これは本質的に、”無制限の計算能力（つまり、必要な数のコンピューター）を持っていれば、多項式時間で問題を解決することができます”と言う別の方法です。 しかし、より直感的には、それは現在、迅速な（多項式時間）十分な答えを見つける方法がないが、問題の解決策を提供すれば（多項式時間で）迅速に検証できる問題のクラスを指している。 ここで検証されたという用語は、提供された解決策が実際に正しいことを確認できることを意味します。
明らかに、上記の定義に基づいて、P≤NP。, この抽象的な問題を説明するための例を見てみましょう。
最も一般的で効果的な例の一つは数独です。 未解決の数独グリッド（例えば9×9）を考えると、アルゴリズムを解くのにかなりの時間がかかります。 ただし、9×9グリッドが100×100または10,000×10,000グリッドに増加すると、問題自体が著しく困難になるため、それを解決するのにかかる時間は指数関, しかし、解決された数独グリッド（9×9）を考えると、サイズが10,000×10,000にスケールされていても、特定の解が実際に正しいことを確認するのはかなり それは遅くなりますが、解をチェックする時間は遅い速度で（多項式で）増加します。
ナップザック問題や旅行セールスマン問題など、他にも多くのNP問題があり、解決するのは難しいが検証が迅速であるという点で似ています。, ここで解決しようとしている根本的な問題は次のとおりです。
NP正解をすばやく認識できるということは、それらを見つける素早い方法もあることを意味しますか？
そうであれば（つまり、P=NP）、これはこれらのNP問題をどのように見ているかを大きく変える可能性がありますこれらの問題をすべて解決するための素早い方法があることを意味するため、まだどのように理解できていないだけです。
これが十分に複雑でない場合は、それを盛り上げましょう。,
これらのNP問題の中には、研究者がNP完全問題と呼ぶすべての問題の王が存在します。 形式的には、それらはそれぞれの問題の集合であり、他のNP問題は多項式時間で還元され（後述）、その解は多項式時間で検証される可能性があります。 これは、任意のNP問題がNP完全問題に変換できることを意味します。
非公式には、それらはNP問題の”最も難しい”ものです。, したがって、いずれかのNP完全問題を多項式時間で解くことができれば、すべてのNP完全問題は多項式時間で解くことができ、NPにおけるすべての問題は多項式時間で解くことができる（すなわちP=NP）。 最も有名な例は旅行のセールスマン問題である。
NP困難な問題と呼ばれる一連の問題も存在します。, これらの問題は少なくともNP問題と同じくらい難しいですが、多項式時間で解決する必要がある条件はありません。 これは、NP困難な問題が必ずしもNPクラスの一部であるとは限らないことを示唆している。 例はチェスボードを解くことです—チェスボードの状態が与えられれば、与えられた状態での与えられた動きが実際に最適な動きであるかどうかを伝えることはほとんど不可能です。 形式的には、NP困難な問題に対する解を検証する多項式時間アルゴリズムは存在しない。,
この二つをまとめると、NP完全問題はそれがNP困難であることを意味しますが、NP困難な問題はそれがNP完全であることを意味するものではありません。
NP完全性の定義
問題Lは、次の場合にNP完全です。
- LはNP困難です。
- LはNPに属します。
以下の図（左辺に焦点を当てる）は、物事をより明確にする必要があります。,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
非公式には、問題L1は別の問題L2に還元することができます：
- L1の任意のインスタンスをL2のインスタンスとしてモデル化することができます
- 後者の解は前者の解を提供し、その逆もまた同様です
これを直感的に理解するためには、L1がL2に還元可能な場合、L1はL2に還元されなければならない。
L1がL2に還元可能な場合、L1はL2のインスタンスとしてモデル化されなければならない。l2と同じくらい難しいです。 逆に、L2は少なくともL1と同じ硬さでなければなりません。
数学的には、これはL1∈p L2（”L1はL2に多項式還元可能である”と読む）として表される。,
