平方根和問題
コンピュータサイエンスにおける未解決問題
平方根和問題のチューリング実行時複雑度はどれくらいですか?
コンピュータサイエンスにおけるさらなる未解決問題

平方根和問題(SRS) は、数値解析の分野における計算決定問題であり、計算幾何学に応用されています。

定義

SRSは次のように定義される：[ 1 ]

正の整数と整数tが与えられた場合、かどうかを判断します。1つの1、…、1つのけ{\displaystyle a_{1},\ldots ,a_{k}}∑私＝1け1つの私≤t{\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}\leq t}

別の定義は次のとおりです。

正の整数およびが与えられた場合、かどうかを判断します。1つの1、…、1つのけ{\displaystyle a_{1},\ldots ,a_{k}}b1、…、bけ{\displaystyle b_{1},\ldots ,b_{k}}∑私＝1け1つの私≤∑私＝1けb私{\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}\leq \sum _{i=1}^{k}{\sqrt {b_{i}}}}

この問題は1981年に提起された[ 2 ]。おそらくそれ以前にも提起されていたと思われる。

実行時の複雑さ

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

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

Allender、Burgisser、Pedersen、Miltersen [ 6 ]は、SRSが計数階層（ PSPACEに含まれる）に存在することを証明した。具体的には、SRSが計数階層の第4レベルで あるP PP PP PPに存在することを示している。

平方根が単項式で与えられる問題のバージョンは、 P/polyという、はるかに低い計算量になります。これは、多項式サイズの回路で解けることを意味しますが、そのような回路を見つけるのは容易ではないかもしれません。[ 7 ]

分離境界

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

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

特に興味深いのは、r( n , k )がO(poly( k ,log( n ))の範囲内にあるかどうかである。もしそうであれば、SRSはチューリングマシンモデルにおいて多項式時間で解けることを意味する。現在知られている境界値には以下のようなものがある。

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

アプリケーション

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

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

半正定値計画法との関係

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

拡張機能

KayalとSaha [ 15 ]はこの問題を整数から多項式へと拡張した。彼らの結果は、特別なクラスの整数に対するSRSの解を示唆している。

参考文献

  1. ^ a b Goemans, Michel X. (1997-10-01). 「組合せ最適化における半正定値計画法」 .数理計画. 79 (1): 143– 161. doi : 10.1007/BF02614315 . ISSN  1436-4646 . S2CID  17221714 .
  2. ^ O'Rourke, Joseph (1981). 「上級問題6369」.アメリカ数学月刊. 88 (10): 769.
  3. ^ Tiwari, Prasoon (1992-12-01). 「単位コスト代数RAMで解く方が簡単な問題」 . Journal of Complexity . 8 (4): 393– 397. doi : 10.1016/0885-064X(92)90003-T . ISSN 0885-064X . 
  4. ^ 「平方根和の複雑さ | Open Problem Garden」 . garden.irmacs.sfu.ca . 2024年1月1日閲覧。
  5. ^ "CSDL | IEEE Computer Society" . www.computer.org . 2024年1月1日閲覧。
  6. ^エリック・アレンダー;ピーター・ビュルギッサー;ケルトゴー・ペダーセン、ヨハン。ミルターセン、ピーター・ブロ (2009 年 1 月)。「数値解析の複雑さについて」。SIAM ジャーナル オン コンピューティング。38 (5): 1987–2006。土井: 10.1137/070697926。ISSN 0097-5397。 
  7. ^ Balaji, Nikhil; Datta, Samir (2024). 「USSR is in P/poly」. Parter, Merav; Pettie, Seth (編). 2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8–10, 2024 . SIAM. pp.  151– 159. arXiv : 2310.19335 . doi : 10.1137/1.9781611977936.15 .
  8. ^ Demaine, Erik D.; Mitchell, Joseph; O'Rourke, Joseph. 「TOPP: 問題33: 平方根の合計」 . topp.openproblem.net . 2024年1月1日閲覧。
  9. ^ Qian, Jianbo; Wang, Cao An (2006-12-16). 「整数の平方根の和を比較するにはどの程度の精度が必要か？」情報処理レター. 100 (5): 194– 198. doi : 10.1016/j.ipl.2006.05.002 . ISSN 0020-0190 . 
  10. ^ Burnikel, C.; Fleischer, R.; Mehlhorn, K.; Schirra, S. (2000-05-01). 「根号を含む算術式に対する強力かつ容易に計算可能な分離境界」 . Algorithmica . 27 (1): 87– 99. doi : 10.1007/s004530010005 . ISSN 1432-0541 . S2CID 34502818 .  
  11. ^ Cheng, Qi; Meng, Xianmeng; Sun, Celi; Chen, Jiazhe (2010年4月). 「格子縮約による平方根の和の境界設定」 .計算数学. 79 (270): 1109– 1122. arXiv : 0905.4487 . Bibcode : 2010MaCom..79.1109C . doi : 10.1090/S0025-5718-09-02304-7 . ISSN 0025-5718 . 
  12. ^ Cheng, Qi; Li, Yu-Hsin (2011-09-09). 「小さな整数の平方根の和の最小差について」 .理論計算機科学. 412 (39): 5458– 5465. doi : 10.1016/j.tcs.2011.06.014 . ISSN 0304-3975 . 
  13. ^アイゼンブランド、フリードリヒ；ヘーベル、マシュー；シンガー、ネタ (2023). 「部分空間定理による平方根の和の改良された境界」arXiv : 2312.02057 [ cs.CG ].
  14. ^ Etessami, Kousha; Yannakakis, Mihalis (2008-11-11). 「再帰的並行確率ゲーム」 .論理的コンピュータサイエンス手法. 4 (4) 1196. arXiv : 0810.3581 . doi : 10.2168/LMCS-4(4:7)2008 . ISSN 1860-5974 . 
  15. ^ Kayal, Neeraj; Saha, Chandan (2012-11-01). 「多項式の平方根の和と関連問題について」 . ACM Transactions on Computation Theory . 4 (4): 9:1–9:15. doi : 10.1145/2382559.2382560 . ISSN 1942-3454 . S2CID 7225729 .  
「 https://en.wikipedia.org/w/index.php?title=Square-root_sum_problem&oldid=1327677290」より取得