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

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

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

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

この分野で最も重要な問題と考えられており、クレイ数学研究所は、最初の正しいデモを開発する人々に100万米ドルの賞を提供しています。
human
よく理解していません。例を挙げていただけませんか？平方根などの簡単な数学操作で説明するかもしれません。
gpt
正方形の根で説明するのは少し複雑ですが、数独であなたに説明することができます。
9x9 Sudokuには、6,670,903,752,021.072.936,960の組み合わせ、多くの組み合わせがあります。これで、20x20のsudokuを持つことができる組み合わせの数を想像してみてください。
人間はアルゴリズムを作成して、それらのアルゴリズムを除くすべてのそれらの間に正しい組み合わせを見つけるために数独のサイズに依存しているため、20x20の数独に適用すると、解決策を見つけるのにはるかに時間がかかります。
問題とPが望んでいるのは、このタイプの問題のために、これらの問題の超迅速なアルゴリズムを作成する可能性のあるソリューションのサイズに依存しないアルゴリズムがあることを実証することですが、これまでのところ誰もそれを解決する層ではありません。
human
SudokuはPまたはNPの問題ですか？
gpt
SudokuはNP（非類似の）問題と見なされます。理論的には、多項式時間に、つまり、入り口の大きさの多項式に比例した時間に見られる最適な解がないからです。これは、発音を解決するために必要な時間が、パズルの複雑さの増加とともに指数関数的に成長できることを意味します。