問題が VPN の問題であることを証明するにはどうすればよいですか?コンピュータ科学者は簡単な方法を発見した

P/NP 問題は、計算複雑性の分野における未解決の問題です。人々は、「すべての計算問題を妥当な時間内に効率的に解決できるか」という疑問に対する答えを見つけようとしてきました。

妥当な時間とはどのくらいでしょうか?実際、宇宙の終わりまでに解決できる問題はすべて、妥当な時間内に解決されると考えられます。しかし、多くの問題は妥当な時間内に解決するのが難しいように思われ、その難しさの数学的証明が必要になります。

2021年の研究ではこれらの疑問に答え、問題の大部分は効果的に解決するのが難しいことが確認されました。

ワシントン大学のポール・ビーム氏はこの研究について次のようにコメントした。「この研究は、ちょうど山登りと同じように、計算理論の道の途中にある休憩地点だ。」

この研究の背後にいる3人の研究者：コンピューター科学者のSrikanth Srinivasan氏（左）、Nutan Limaye氏（右上）、Sébastien Tavenas氏。

この研究で検討された問題は加算と乗算のみを対象としていましたが、これらの問題を特定の方法（加算と乗算を交互に行う特定のパターン）で解くように制限すると、非常に難しくなりました。

驚くべきことに、この研究では新たな枠組みやツールは使用されず、その代わりに著者らは、高等研究所の数学教授であるウィグダーソン氏とエルサレム・ヘブライ大学のノアム・ニサン氏が数十年にわたって研究してきた数学的障壁を回避することに成功した。

「この障害を回避する非常に簡単な方法があることに気づいた」と、デンマークのオーフス大学の共著者スリカンス・スリニバサン氏は語った。「不可能だと思っていたことができるほど簡単なら、もっと良い方法があるはずだ」

重要な質問

コンピュータの出現後、科学者たちはコンピュータ アルゴリズムが多くの問題を解決できることを発見しましたが、これらのアルゴリズムには実際の計算時間よりも長い時間がかかることもありました。

彼らは、問題の大きさや小ささに関係なく、一部の問題は解決するのが本質的に難しすぎるのではないかと疑い始めました。たとえば、グラフでは、ハミルトン経路、つまり各頂点を正確に 1 回通過する経路が存在するかどうかを判断することが重要な問題です。ポイント (およびエッジ) の数を増やすと、そのようなパスが存在するかどうかを判断するのにかかる時間が長くなりますが、グラフのサイズが大きくなるにつれて、最良のアルゴリズムでも指数関数的に時間がかかるようになり、この問題の解決は非現実的になります。

コンピュータ科学者は、あるクラスの問題における難しい問題を何らかの方法で効率的に解決できるアルゴリズムは、同様に難しい他の問題の解決策に変換できることを証明しようとします。彼らはこのクラスの問題を NP 問題と呼びます。

もちろん、それほど難しくなく、解決にそれほど時間がかからない問題もたくさんあります。これらの問題の多くは、ある意味で同等であり、このクラスの問題は P 問題と呼ばれます。彼らは、NP 問題は確かに P 問題よりも難しく、NP 問題は効果的に解決できないと信じています。しかし、証拠がなければ、この考えはおそらく間違っているでしょう。

そこでコンピューター科学者たちは、NP 問題が実際に困難であることを証明する方法を模索し始めました。そのためには、NP 問題を解決するには指数関数的に長い時間がかかることを証明する必要がありますが、これを証明するのは簡単ではありません。

「難しい」とはどの程度難しいのでしょうか?

加算と乗算のみを必要とする特定の問題セットを考えてみましょう。たとえば、点の集合が与えられた場合、加算と乗算のみを使用して、点に関するデータを使用して、すべての可能なハミルトン経路 (存在する場合) を計算できます。

一部の算術問題 (ハミルトン経路の計算など) では、問題のサイズが大きくなるにつれて時間がかかります。 1979 年、ハーバード大学のレスリー・バリアントは、多くの算数の問題は「難易度」の点では同等である一方、他の問題は「難易度がない」という点では同等であることを証明しました。後にコンピューター科学者たちは、彼にちなんでこれら 2 種類の問題をそれぞれ VNP と VP と名付けました。

P 問題や NP 問題と同様に、VNP 問題の難しさは証明できません。VNP 問題は NP 問題に基づいているため、NP 問題よりも難しいということだけがわかっています。たとえば、パスを計算するには、まずパスが存在するかどうかを判断する必要があります。

「これはNPよりも難しいので、難しいことを証明するのは簡単なはずだ」とシュピルカ氏は語った。

その後の数十年間、コンピュータ科学者は P 対 NP 問題よりも VP 対 VNP 問題で大きな進歩を遂げましたが、そのほとんどは Valiant が作成した代数的複雑性と呼ばれるサブフィールドに限定されていました。 Limaye、Srinivasan、Tavenas による最近の研究以前は、算術上の問題が一般的に存在するかどうかを判断することは依然として困難でした。

調整多項式

この新しい研究は、コンピューター科学者が加算と乗算の問題をどのように考えているかを探るのに役立ちます。数学的には、これらの問題は、加算および乗算される変数で構成される多項式 (x^2 + 5y + 6 など) の形式で記述できます。

ハミルトン経路の計算など、特定の問題については、それを表す多項式を構築できます。たとえば、各ポイントとエッジを変数で表すと、ポイントとエッジを追加するたびに、多項式に変数を追加できます。

ハミルトン経路の計算などの算術問題が難しいことを証明するには、点と辺が追加されるにつれて、対応する多項式を指数時間で解くためにより多くの演算が必要になることを示す必要があります。たとえば、x^2 には 1 つの演算 (x * x) が必要ですが、x^2 + y には 2 つの演算 (x * x の後に y を加算) が必要です。演算回数は多項式のサイズと呼ばれます。

しかし、多項式のサイズを決定するのは困難です。たとえば、多項式 x^2 + 2x + 1。これはサイズが 4 (2 つの乗算と 2 つの加算) であるように見えますが、多項式は 2 つの合計の積 (x + 1)(x + 1) として書き直すことができ、これにより演算が 2 つの加算と 1 つの乗算に減ります。多くの場合、問題のサイズが大きくなり、多項式に変数が追加されるにつれて、数学的変換によって問題を簡素化し、サイズを縮小することができます。

ヴァリアントの研究から数年後、コンピューター科学者たちは、問題の規模を解析しやすいものにする方法を発見した。これを実現するために、彼らは「深さ」と呼ばれる特性を提案しています。これは、多項式が和と積を切り替える、つまり交互に切り替える回数を指定します。たとえば、多項式 x^2 + 2x + 1 は積 (x^2 と 2x など) の合計なので、深さは 2 になります。対照的に、式 (x + 1)(x + 1) の深さは 3 です。これは、積の合計として計算された 0 + (x + 1)(x + 1) と同じ深さであるためです。

多項式を単純化するために、コンピューター科学者は、問題が拡大しても和と積のパターンが変化しない、定数深度と呼ばれる特性を持つ固定形式に多項式を制限します。これにより、サイズがより固定され、多項式のサイズは深さが増すにつれて小さくなります。ある一定の深さを表す式を式と呼びます。一定の深さにより、多項式の研究がさらに進歩します。

魔法の深さ

1996 年に、Nisan と Wigderson による論文では行列乗算の問題の解決に焦点を当て、2 つの方法で問題を簡略化しました。まず、深さが一定の式（深さ 3）を使用して表現します。第二に、彼らは、各変数の最大指数が 1 である特定の単純な構造を持つ式のみを考慮したため、元の問題は「多重線型」問題になりました。

コンピュータ科学者は、多項式のサイズが指数関数的に増加する（指数関数的増加率に匹敵する）という犠牲を払って、特定の問題を比較的単純な集合多重線形構造に変換できることを発見しました。

その後、ニサンとウィグダーソンは、行列乗算問題は行列が大きくなるにつれて解くのに指数関数的な時間がかかることを示しました。言い換えれば、彼らは重要な問題が難しいことを示し、一連の問題全体が難しいことを示す努力をしたのです。ただし、その結果は、単純で集合的な多重線形構造を持つ式にのみ適用されます。

レスリー・ヴァリアント

多項式の深さを増やすと、そのサイズが小さくなる傾向があります。時間の経過とともに、コンピューター科学者はこれら 2 つの特性間のトレードオフをより正確にしてきました。彼らは、深さ 3 のアンサンブル多線形多項式に 2 つの深さレベルを追加すると、そのアンサンブル多線形構造のサイズ増加をバランスさせることができることを示しています。深さ 5 の構造化された式に指数時間がかかる場合、一般的な構造化されていない深さ 3 の式にも指数時間がかかります。

Srikanth Srinivasan らによる新しい研究では、行列乗算問題に対する深さ 5 の多重線形定式化セットが指数関数的に増加することが示されています。つまり、一般的な深さ 3 の式も指数時間がかかります。そして、同様のパターンがすべての深さ（3 と 5 だけでなく）に当てはまることを示しました。この関係により、彼らは、任意の深さの同じ問題に対する一般的な公式のサイズが、問題のサイズに応じて指数関数的に増加することを示しました。

また、深さが何であっても、一定の深さの式を使用して行列の乗算を表現することは難しいことも示しました。

この研究の結果は、算数の問題が「難しい」とき、つまり一定の深さの式を使って表現できないときについて、初めて一般的な理解を提供するものである。行列乗算の特定の問題は VP 問題として知られています。また、VP 問題は、一定の深さに制限されていない場合は比較的簡単であることが知られているため、一定の深さが問題の「難しさ」の原因であることがわかります。

VNP の質問は VP の質問よりも難しいですか?新しい結果はこれを直接示すものではなく、一定深度の式が難しいことを示しているだけです。しかし、これは、VNP 問題が VP 問題と同等ではないことを証明する上で、依然として重要なマイルストーンです。

より大きな P と NP の問題に関しては、いつか答えが見つかるだろうと楽観視できるようになりました。結局のところ、難しい問題を解決するには、まずどの方向が絶望的であるかを知る必要があります。