Sum of radicals とは

計算複雑性理論では、入力サイズ、すなわちこの合計を表すのに必要なビット数に依存して、ラジカルの和に関するいくつかの情報を多項式時間で計算できるかどうかの問題がある。一般的に2点間のユークリッド距離の計算には平方根の計算が必要なため、多角形の外周や多角形の長さは、ラジカルの合計の
ラジカルの合計は、ラジカルの有限の線形結合として定義される:
i = 1 n k i x i r i , {\displaystyle \sum _{i=1}^{n}k_{i}{\sqrt[{r_{i}}]{x_{i}}},}
ここで n , r i {\displaystyle n,r_{i}} は自然数、 k i , x i {\displaystyle k_{i},x_{i}} は実数です。
コンビナトリアルキャラクタの計算幾何学における最も理論的な研究は、無限精度の実RAMの計算モデル、すなわち実数とその演算が無限の精度で実数の入力サイズと基本的な操作は定数です。しかし、数値の入力サイズがその表現に必要なビット数である計算機の複雑さ、特にコンピュータ代数の研究があります。
特に、計算幾何学に関心があるのは、ラジカルの和の符号を決定する問題である。例えば、すべての頂点が整数座標を有する多角形経路の長さは、ピタゴラス定理を整数平方根の和として表現することができるので、ある経路がユークリッド最短経路において他の経路よりも長いか短いかを決定するために問題では、第1パスの長さを減算した式の符号を求める必要があります。この式はラジカルの和です。
同様に、根本問題の和は、ユークリッド距離の最小重み三角測量の問題に内在しています。
1991年、Blermerは、ラジカルの合計がゼロか、より一般的にはそれが有理数を表すかどうかを決定する多項式時間モンテカルロアルゴリズムを提案した。 Blermerの結果は、ラジカルの和の符号を見出す計算上の複雑さを解決しないが、後者の問題がクラスNPにある場合、それは共NPにもあることを意味する。