human
n対npの問題は何ですか？そして、どのように結果を見つけることができますか？
gpt
NPとPの複雑さクラスの関係は、コンピューター科学者のStephen Cookが計算の複雑さの理論がまだ答えることができていないことを初めて策定した質問です。本質的に、質問はp = npが完全ですか？つまり、SI/NOタイプの問題に対する肯定的な解決策を「検証」することが可能である場合（「迅速」は多項式時間に「迅速」を意味します）、答えを迅速に「取得」することができますか？

計算の複雑さで一般的に研究されるリソースは次のとおりです。

 - 時間：アルゴリズムが問題を解決するために使用する実行手順の数へのアプローチを通じて。

 - スペース：問題を解決するために使用されるメモリの量へのアプローチを通じて。

この分野で最も重要な問題と考えられており、クレイ数学研究所は、最初の正しいデモを開発する人々に100万米ドルの賞を提供しています。
human
よく理解していません。例を挙げていただけませんか？平方根などの簡単な数学操作で説明するかもしれません。
gpt
NP対問題Pは、特定の例でよりよく理解できます。たとえば、因数分解を統合する問題を考慮してください。これは、増殖するときに特定の数を生成する2つの整数を見つけることを意味します。たとえば、15の係数を見つけるために、2つの数値は3と5です。

数字123456789などの多数の要因を見つけなければならなかった場合、それを行う最も簡単な方法は、格付けされた2つの数値を見つけるまで、1から与えられた数値まですべての数値を試してみることです。ただし、これは徹底的な検索になります。つまり、解決策を見つけるのに長い時間がかかることを意味します。したがって、非最適解決策は非皮質の時間に見られるため、積分因数分解の問題はNPクラスにあります。

これで、クラスPで同等の問題を見つけるために問題の減少を適用すると、平方根を使用できます。123456789の平方根を計算した場合、11111を取得します。11111を11111で掛けると、123456789の因子を形成する2つの整数を掛けると同じ結果が得られます。これは、因子を見つけることを意味します。 123456789の徹底的な検索を実行する代わりに、平方根を計算して結果を掛けることができます。
human
物理的なオブジェクトで説明できますか？箱、ボール、果物...わからない...
gpt
さまざまな種類の果物（リンゴ、ナシ、オレンジなど）の果物のスタックがあり、その種類に応じてボックスに分類したいと思います。多項式時間Pでアルゴリズムを使用すると、各果物を他のすべての果物と比較して、対応するボックスに置くことができます。このプロセスには、果物の数に関して線形時間がかかります。

ただし、非決定的アルゴリズム（NP）を使用すると、他の果物と比較せずに、最初の果物を単純に検証して決定することができます。このプロセスは、1つの果物を同時に検証するだけであるため、果物の数に関して多項式時間がかかります。

つまり、P vs NPの問題は、すべてのNPの問題を多項式時間で解決できるかどうかという問題を提起します。