数学者は、数学とコンピュータサイエンスの境界で30年前の問題を解決しました。彼は同僚がそのシンプルさに驚かせる革新的でエレガントな証拠を使用しました。
アトランタのエモリー大学の数学の助教授であるハオ・ファンは、感度予測と呼ばれる数学的アイデアを証明しました。その感度です）。
数学者が最初に感度予測を提案した後（それを証明せずに）数十年で、理論的なコンピューター科学者は、情報を処理する最も効率的な方法を決定するのに大きな影響があることに気付きました。
この分野の他の専門家によると、黄氏の証明について注目すべきことは、黄氏がそれを引き離したことだけでなく、彼がそれをしたエレガントで簡単な方法でもあります。彼の証明は公式に査読されたり、数学の雑誌に発表されたりしていない。しかし、ファンが7月1日オンラインで公開した直後に、彼の同僚はすぐにそれを事実として受け入れました。
「このような発表があるときはいつでも」、テキサス大学オースティン校の理論コンピューター科学者スコットアーロンソンはブログに次のように書いています。これは、残りの1％のケースの1つです。証明が正しいと確信しています。なぜですか？読んで理解したので、約30分かかりました。」
ピッツバーグのカーネギーメロン大学で数論を研究しているコンピューターサイエンスの教授であるRyan O'Donnellは、Huangの証明は1つのツイートで要約できると指摘しました。
フアンは実際に何を証明したのですか？
簡単にするために、それぞれが1単位の長さの辺を持つ3D立方体を想像してください。この立方体を3D座標系に配置すると（3方向の測定値があることを意味します）、1つのコーナーの座標は（0,0,0）となり、その隣のコーナーは（1,0,0）になる可能性があります。その上の1つは（0,1,0）のようになります。 （0,0,0）、（1,1,0）、（1,0,1）、および（0,1,1）は隣人のペアがなくても、半分のコーナー（4つのコーナー）を取ることができます。 t隣人。これは立方体を見るとわかりますが、すべての座標が複数の座標で異なるため、これもわかります。
ヘブライ大学の数学者、ギル・カライ氏は、感度の推測は、高次元の立方体、つまり超立方体の角の半分以上をとったときの隣人の数を見つけることに関するものだと語った。ハイパーキューブの座標は1と0の文字列として記述できます。次元数は文字列の長さです。KalaiはLive Scienceに語った。たとえば、4Dハイパーキューブの場合、16の異なるポイントがあります。これは、4桁の1と0の16の異なる文字列を意味します。
次に、ハイパーキューブ上の半分プラス1の個別のポイントを選択します（4Dハイパーキューブの場合、これは、合計16個のポイントから9個または8 + 1個の異なるポイントを選択することを意味します）。
この小さいセットから、最も近傍を持つポイントを見つけます-何ですか 最小 それが持つことができる隣人の数？ （ネイバーは1つの数字だけ異なります。たとえば、1111と1110はネイバーです。1桁を交換するだけで1桁目を2桁目に変換できるためです。）
フアンは、このコーナーには少なくとも桁数の平方根（この場合は4の平方根）と同じ数の近傍が必要であることを証明しました。これは2です。
低次元の場合、チェックするだけでこれが正しいことを確認できます。たとえば、隣人のキューブ（または「文字列」）の16の座標を確認することはそれほど難しくありません。ただし、キューブにディメンションを追加するたびに、文字列の数は2倍になります。そのため、問題をすぐに確認することが難しくなります。
30桁の長さの文字列のセット（30次元の立方体の角の座標）には、10億を超えるさまざまな文字列が含まれています。つまり、立方体の角は10億を超えています。 200桁の長さの文字列では、novemdecillionを超えます。これは、1億億、10億、10億、または1の後に60個のゼロが続きます。
これが数学者が証明を好む理由です。彼らは簡単なものだけでなく、すべての場合に何かが真であることを示しています。
「もし ん 100万に等しい-これは、100万長の文字列があることを意味します。つまり、2 ^ 1,000,000-1を取り、1を追加すると、1,000の近傍を持つ文字列があることになります-100万の平方根、 「カライは言った。
感度予測における最後の大きな進歩は1988年に起こったとカライ氏は述べ、研究者は1つの文字列が少なくとも対数を持つ必要があることを証明した ん 隣人。これははるかに少ない数です。 1,000,000の対数は6です。したがって、Huangの証明は、少なくとも994の他の近隣がそこにあることを発見しました。
エレガントで「神秘的な」証明
「それは非常に神秘的です」とカライは黄の証拠について言った。 「これは数学の多くの分野で非常に重要な方法である「スペクトル法」を使用します。しかし、それは新しい方法でスペクトル法を使用します。それはまだ神秘的ですが、スペクトル法を使用するこの新しい方法が徐々により多くのアプリケーション。」
本質的に、Huangは行と列（行列と呼ばれる）の数値の配列を使用してハイパーキューブを概念化しました。アーロンソン氏はブログで、ファンが「魔法のようにすべてを機能させる」-1と1の異常な配列でマトリックスを操作するまったく予期しない方法を見つけたと考えています。
黄氏は「このマトリックスを採用し、非常に独創的で神秘的な方法で修正した」とカライ氏は語った。 「まるでオーケストラがいて、彼らがいくつかの音楽を演奏しているようです。それから、一部のプレーヤーに、私にはわかりませんが、彼らの頭に立つと、音楽は完全に異なります-そのようなものです。」
その異なる音楽が推測を証明する鍵であることが判明したとカライは言った。数学者はこの方法がなぜ機能するのかを理解しているが、この新しい「音楽」や他のどのような場合に役立つか興味深いかを完全には理解していないため、それは不思議だと彼は言った。
「30年間、進展はありませんでした。その後、ハオフアンはこの問題を解決しました、そして彼は答えがの平方根であることを非常に簡単な証拠に見つけました ん「しかし、この30年間、人々はこの質問がコンピューティングの理論において非常に重要であることに気づきました。」
黄氏の証明は、コンピューターサイエンスの分野を前進させるので、エキサイティングです。しかし、それはまた、新しい方法を導入したので注目に値します、そして、数学者はまだ他に黄の新しい方法が彼らが達成することを可能にするかもしれないと確信していません。
