ギズモードの記事で「奇数偶数素数はわかるけど、P≠NP予想がわからない人類は、P≠NP予想やナビエ–ストークス方程式の解がわかるAIに圧倒されるでしょう。」なんていう文言があり、私はP≠NP予想がわからない人間なのでこれが何なのか調べてみました。
P≠NP予想をネットで調べているとNP完全とNP困難の説明が出てくるわけですが、このNP完全の定義に意味の分からない部分が含まれています。
Wikipediaによれば…
(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、 かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。
…だそうで。
意味が分からないのはこの定義の(2)です。たとえばハミルトン経路問題は上記のWikipediaのページにも記載されている通り、NP完全な問題なのでしょう。ということは、クラスNPに属する任意の問題はハミルトン経路問題に多項式時間還元（帰着）できる？？？
問題の帰着というと、複雑そうに見える問題を、解き方の知られている問題に読み替えることを言うイメージですが、任意の問題を（多項式時間で）帰着できるというのはどういう意味なのか想像がつかないです。
2023/02/18 19:00 追記
ChatGPTに聞いてみました。
掛居「クラスNPに属する任意の問題から多項式時間還元というのはどういうことか、例を挙げて説明してもらえますか？」
ChatGPTの答え↓
「クラスNPに属する任意の問題から多項式時間還元可能」というのは、「NP」というクラスに属するどの問題でも、別の問題に多項式時間で変換できるということを意味します。この変換方法を使うことで、変換元の問題の解法を使って変換先の問題を解くことができるようになります。
多項式時間還元の一般的な手順は以下のようになります。
変換元の問題を、変換先の問題に変換するための関数を定義します。 変換先の問題のインスタンスを、変換元の問題のインスタンスに変換するための手順を定義します。 変換元の問題の解法を使って、変換先の問題を解きます。 以下に例として、SAT（充足可能性問題）と3-SAT（3-CNF充足可能性問題）という2つの問題を考えてみます。SAT問題は、ブール式が与えられたとき、その式が充足可能かどうかを判定する問題です。一方、3-SAT問題は、3項式のANDの形で表されるブール式が与えられたとき、その式が充足可能かどうかを判定する問題です。
この場合、SAT問題から3-SAT問題への多項式時間還元を行うことができます。具体的には、SAT問題の任意のブール式を、以下のように変換することで、3-SAT問題のインスタンスに変換することができます。
全ての式を3項式に変換する。 新しい変数を追加し、それを用いて式をANDでつなげる。 この変換によって、SAT問題のインスタンスを3-SAT問題のインスタンスに多項式時間で変換することができます。そして、SAT問題が充足可能である場合は、3-SAT問題も充足可能であり、充足不可能な場合も充足不可能であることが示されています。したがって、SAT問題から3-SAT問題への多項式時間還元を使って、SAT問題を解くことができます。
この回答ができるのはすごいんですが、SAT問題というのは特定の問題であって「クラスNPに属する任意の問題」ではないはずですね。とはいえ、「多項式時間還元」をちゃんと調べれば答えにいきつきそうな方向性は見出せた気がします。
