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

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

Сумма радикалов определяется как конечная линейная комбинация радикалов:

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

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

Большинство теоретических исследований в области вычислительной геометрии комбинаторного характера предполагают вычислительную модель реального ОЗУ бесконечной точности, т. е. абстрактный компьютер, в котором действительные числа и операции над ними выполняются с бесконечной точностью, а входной размер действительного числа и стоимость элементарные операции являются константами. ^[2] Однако существуют исследования вычислительной сложности, особенно в компьютерной алгебре , где входной размер числа — это количество бит, необходимых для его представления. ^[3]

Особый интерес в вычислительной геометрии представляет проблема определения знака суммы радикалов . Например, длина многоугольного пути, в котором все вершины имеют целочисленные координаты, может быть выражена с помощью теоремы Пифагора как сумма целых квадратных корней, поэтому, чтобы определить, является ли один путь длиннее или короче другого в евклидовом кратчайшем пути задача, необходимо определить знак выражения, в котором длина первого пути вычитается из второго; это выражение представляет собой сумму радикалов.

Аналогичным образом проблема суммы радикалов присуща задаче триангуляции минимального веса в евклидовой метрике .

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

См. также

Ссылки

^ Мюльцер, Вольфганг; Роте, Гюнтер (2008). «Триангуляция минимального веса NP-трудна». Журнал АКМ . 55 (2): А11:1–А11:29. arXiv : cs/0601002 . дои : 10.1145/1346330.1346336 . МР 2417038 .
^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN 978-0-387-96131-6 . 1-е издание: 2-е издание, исправленное и дополненное, 1988 г.; Русский перевод, 1989.
^ Справочник по компьютерной алгебре , 2003, ISBN 3-540-65466-6
^ Jump up to: ^а ^б Блёмер, Йоханнес (1991). «Вычисление сумм радикалов за полиномиальное время». [1991] Материалы 32-го ежегодного симпозиума по основам информатики . стр. 670–677. дои : 10.1109/SFCS.1991.185434 . ISBN 978-0-8186-2445-2 . S2CID 195840518 . .

[mulzer-1] Мюльцер, Вольфганг; Роте, Гюнтер (2008). «Триангуляция минимального веса NP-трудна». Журнал АКМ . 55 (2): А11:1–А11:29. arXiv : cs/0601002 . дои : 10.1145/1346330.1346336 . МР 2417038 .

[2] Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN 978-0-387-96131-6 . 1-е издание: 2-е издание, исправленное и дополненное, 1988 г.; Русский перевод, 1989.

[3] Справочник по компьютерной алгебре , 2003, ISBN 3-540-65466-6

[blomer-4] Jump up to: ^а ^б Блёмер, Йоханнес (1991). «Вычисление сумм радикалов за полиномиальное время». [1991] Материалы 32-го ежегодного симпозиума по основам информатики . стр. 670–677. дои : 10.1109/SFCS.1991.185434 . ISBN 978-0-8186-2445-2 . S2CID 195840518 . .

[1]

[2]

[3]

[4]