Сумма радикалов

В математике сумма радикала s определяется как конечная линейная комбинация корней n- й степени :

${\displaystyle \sum _{i=1}^{n}k_{i}{\sqrt[{r_{i}}]{x_{i}}},}$

где — натуральные числа , а — действительные числа . ${\displaystyle n,r_{i}}$ ${\displaystyle k_{i},x_{i}}$

Частным частным случаем, возникающим в теории сложности вычислений , является проблема суммы квадратных корней , в которой спрашивается, можно ли определить знак суммы квадратных корней с целыми коэффициентами за полиномиальное время . Это важно для многих задач вычислительной геометрии , поскольку вычисление евклидова расстояния между двумя точками в общем случае включает вычисление квадратного корня , и, следовательно, периметр многоугольника или длина многоугольной цепи принимает форму суммы радикалов. ^[1]

В 1991 году Блёмер предложил полиномиальный алгоритм Монте-Карло для определения того, равна ли сумма радикалов нулю или, в более общем случае, представляет ли она рациональное число. ^[2] Результат Блёмера применим более широко, чем проблема суммы квадратного корня, к суммам радикалов, которые не обязательно являются квадратными корнями. Однако его алгоритм не решает проблему, поскольку он не определяет знак ненулевой суммы радикалов. ^[2]

Смотрите также

• Вложенные радикалы
• Теорема Абеля–Руффини

Ссылки

1. Мульцер, Вольфганг; Роте, Гюнтер (2008). «Триангуляция минимального веса NP-трудна». Журнал ACM . 55 (2): A11:1–A11:29. arXiv : cs/0601002 . doi :10.1145/1346330.1346336. MR  2417038.
2. Blömer, Johannes (1991). "Вычисление сумм радикалов за полиномиальное время". [1991] Труды 32-го ежегодного симпозиума по основам компьютерной науки. стр. 670–677. doi :10.1109/SFCS.1991.185434. ISBN 978-0-8186-2445-2. S2CID  195840518..