平方根の和の問題

平方根和問題(SRS) は、数値解析の分野における計算上の決定問題であり、計算幾何学に応用されています。この問題は 1981 年に提起され^{[ 1 ]}、おそらくそれ以前にも提起されていました。

SRSは次のように定義されます。^{[ 2 ]}

正の整数が与えられた場合${\displaystyle a_{1},\ldots ,a_{k}}$整数tで、${\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}\leq t}$。

別の定義としては、次のものがあります。

正の整数が与えられた場合${\displaystyle a_{1},\ldots ,a_{k}}$そして${\displaystyle b_{1},\ldots ,b_{k}}$決定する$\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}\leq \sum _{i=1}^{k}{\sqrt {b_{i}}}}$。

SRSは、実RAMモデルでは多項式時間で解くことができます。^{[ 3 ]}しかし、チューリングマシンモデルにおける実行時間複雑度は、1997年現在未解決です。^{[ 2 ]}主な難点は、この問題を解決するには、平方根を高精度で計算する必要があり、そのためには大量のビットが必要になる可能性があることです。この問題は、未解決問題ガーデンで言及されています。^{[ 4 ]}

Blomer ^{[ 5 ]}は、平方根の和がゼロに等しいかどうかを判定するための多項式時間モンテカルロアルゴリズムを提示している。このアルゴリズムは、より一般的には、任意の根号の和に適用できる。

Allender、Burgisser、Pedersen、Miltersen ^{[ 6 ]}は、SRS が計数階層( PSPACEに含まれる) に含まれることを証明しています。具体的には、SRS が計数階層の第 4 レベルのP ^{PP PP PP}に含まれることを示しています。

平方根が単項式で与えられる問題のバージョンは、 P/polyというはるかに低い複雑さを持つ。これは、多項式サイズの回路で解くことができることを意味するが、これらの回路を見つけるのは容易ではないかもしれない。^{[ 7 ]}

SRSを解決する一つの方法は、絶対差の下限を証明することである。${\displaystyle \left|t-\sum _{i=1}^{k}{\sqrt {a_{i}}}\right|}$または${\displaystyle \left|\sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}\right|}$このような下限は、差と 0 を分離するため、「分離境界」と呼ばれます。たとえば、絶対差が 2 ^{− d}以上であれば、すべての数値をdビットの精度に丸めることができ、SRS をdの多項式時間で解くことができます。

これは、この差の上限を証明するという数学的な問題につながる。r ( n , k )を、この差の最小の正の値と定義する。$${\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}}$$ここで、a _iとb _{i は}1 からnまでの整数です。R ( n , k ) は -log r ( n , k ) と定義され、これはSRSを解くために必要な精度桁数です。r ( n , k )の計算は、オープン問題プロジェクトの未解決問題33 です。 ^{[ 8 ]}

特に、r( n , k )がO(poly( k , log( n ))に含まれるかどうかは興味深い。肯定的な答えが出れば、SRSはチューリングマシンモデルにおいて多項式時間で解けることになる。現在知られている境界は以下のとおりである。

• QianとWang ^{[ 9 ]}は明示的な構成により、任意のkとnに対して、 ${\displaystyle r(n,k)\in O(n^{-2k+3/2})}$、 それで${\displaystyle R(n,k)\geq (2k-3/2)\cdot \log {n}}$この数値はk =2の場合に最適であり、また幅広い整数に対しても最適である。
• バーニケル、フライシャー、メールホルン、シラ^{[ 10 ]}は桁数の上限を証明した。${\displaystyle R(n,k)\in O(2^{2k}\cdot \log {n})}$。
• Cheng、Meng、Sun、Chen ^{[ 11 ]}は、${\displaystyle R(n,k)\in 2^{O(n/\log {n})}\cdot \log {n}}$。
• ChengとLi ^{[ 12 ]}は、${\displaystyle R(n,k)\in 2^{O(n/\log {n})}}$これは、SRSが時間内に解決できることを意味します。$2^{o(k)}\cdot (\log {n})^{O(1)}}$nが o( k log k ) の範囲内である限り、彼らはまた、 r ( n , k ) を時間で計算するアルゴリズムも提示している。${\displaystyle n^{k+o(k)}}$。
• アイゼンブランド、ヘーバーレ、シンガー^{[ 13 ]}は、${\displaystyle r(n,k)\geq \gamma \cdot n^{-2n}}$ここで、ガンマは入力a ₁ ,..., a _nと部分空間定理からのステップに依存する定数です。これは以前の境界を改善します。$\displaystyle r(n,k)\geq \left(n\cdot \max _{i}({\sqrt {a_{i}}})\right)^{-2^{n}}}$。

SRSは計算幾何学において重要です。なぜなら、ユークリッド距離は平方根で与えられ、多くの幾何学的問題（例えば、平面上の最小全域木やユークリッド巡回セールスマン問題）では距離の合計を計算する必要があるからです。

エテッサミとヤナカキス^{[ 14 ]}は、SRSから再帰的同時確率ゲームの終了問題への還元を示している。

SRSは、半正定値計画法の実行可能性問題の単純な特殊ケースであるため、理論的にも重要です。行列を考えてみましょう。${\displaystyle \left({\begin{matrix}1&x\\x&a\end{matrix}}\right)}$この行列は、以下の条件を満たす場合に限り、正半定値行列である。${\displaystyle ax^{2}\geq 0}$、もし${\displaystyle |x|\leq {\sqrt {a}}}$したがって、SRSを解くには、n個の制約を持つ実行可能性問題を次の形式で構築できます。${\displaystyle \left({\begin{matrix}1&x_{i}\\x_{i}&a_{i}\end{matrix}}\right)\succeq 0}$および追加の線形制約${\displaystyle x_{i}\geq 0,\sum _{i=1}^{n}x_{i}\geq k}$結果として得られるSDPは、 SRSが実行可能な場合に限り実行可能である。チューリングマシンモデルにおけるSRSの実行時間複雑度は未解明であるため、SDPの実行可能性についても同様である（1997年時点）。

KayalとSaha ^{[ 15 ]}は、この問題を整数から多項式に拡張した。彼らの結果は、特定のクラスの整数に対するSRSの解を意味する。