Сумма радикалов - Sum of radicals

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

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

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

куда ${ displaystyle n, r_ {i}}$ находятся натуральные числа и ${ displaystyle k_ {i}, x_ {i}}$ находятся действительные числа.

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

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

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

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

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

Рекомендации

^ Вольфганг Мульцер, Гюнтер Роте, "Триангуляция минимального веса NP-трудна", В: Труды 22-го Ежегодный симпозиум по вычислительной геометрии, Седона, 5–7 июня 2006 г., Журнал ACM, Vol. 55, №2, 2008.
^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer-Verlag. ISBN 978-0-387-96131-6. 1-е издание: 2-е издание, исправленное и дополненное, 1988 г .:; Русский перевод, 1989.
^ Справочник по компьютерной алгебре, 2003, ISBN 3-540-65466-6
^ ^а ^б Блёмер, Йоханнес (1991). «Вычисление сумм радикалов за полиномиальное время». [1991] Труды 32-го ежегодного симпозиума основ информатики. С. 670–677. Дои:10.1109 / SFCS.1991.185434. ISBN 978-0-8186-2445-2..

[mulzer-1] Вольфганг Мульцер, Гюнтер Роте, "Триангуляция минимального веса NP-трудна", В: Труды 22-го Ежегодный симпозиум по вычислительной геометрии, Седона, 5–7 июня 2006 г., Журнал ACM, Vol. 55, №2, 2008.

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

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

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

[1]

[2]

[3]

[4]