По каким причинам исследователи в вычислительной геометрии предпочитают модель BSS / real-RAM?

Задний план

Вычисление по действительным числам более сложное, чем вычисление по натуральным числам, поскольку действительные числа являются бесконечными объектами и существует неисчислимо много реальных чисел, поэтому действительные числа не могут быть достоверно представлены конечными строками над конечным алфавитом.

В отличие от классической вычислимости над конечными строками, где различные модели вычислений, такие как: лямбда-исчисление, машины Тьюринга, рекурсивные функции, ... оказываются эквивалентными (по крайней мере, для вычислимости над функциями на строках), существуют различные предложенные модели для вычислений над действительные числа, которые не совместимы. Например, в модели TTE (см. Также [Wei00]), которая является наиболее близкой к классической модели машины Тьюринга, действительные числа представлены с использованием бесконечных входных лент (например, оракулов Тьюринга), и невозможно провести сравнение и отношения равенства между двумя заданными действительными числами (за конечное время). С другой стороны, в моделях BBS / real-RAM, которые похожи на модель машины RAMУ нас есть переменные, которые могут хранить произвольные действительные числа, а сравнение и равенство входят в число атомарных операций модели. По этой и аналогичным причинам многие эксперты говорят, что модели BSS / real-RAM нереалистичны (не могут быть реализованы, по крайней мере, на современных цифровых компьютерах), и они предпочитают TTE или другие эквивалентные модели TTE, подобные теоретической модели эффективной области, Модель Ко-Фридмана и др.

Если я правильно понял , модель вычислений по умолчанию, которая используется в вычислительной геометрии, - это модель BSS (она же real-RAM , см. [BCSS98]).

С другой стороны, мне кажется, что при реализации алгоритмов в вычислительной геометрии (например, LEDA ) мы имеем дело только с алгебраическими числами, и в них не участвуют бесконечные объекты или вычисления более высокого типа (это правильно?). Таким образом, мне кажется (возможно, наивно), что можно также использовать классическую модель вычислений на конечных строках для работы с этими числами и использовать обычную модель вычислений (которая также используется для реализации алгоритмов) для обсуждения правильности и сложности. алгоритмов.

Вопросов:

По каким причинам исследователи в области вычислительной геометрии предпочитают использовать модель BSS / real-RAM? (причины специфической вычислительной геометрии для использования модели BSS / real-RAM)

Каковы проблемы с (возможно, наивной) идеей, о которой я упоминал в предыдущем абзаце? (используя классическую модель вычислений и ограничивая входные данные алгебраическими числами в вычислительной геометрии)

Приложение:

Существует также проблема сложности алгоритмов, в модели BSS / real-RAM очень легко решить следующую проблему:

Даны два набора$S$ натуральных чисел и есть ∑ s ∈ S $T$
?$\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$

Пока не известен эффективный алгоритм целочисленного ОЗУ для его решения. Спасибо Джеффу за пример.

Ссылки:

1. Ленор Блум, Фелипе Кукер, Майкл Шуб и Стивен Смейл, «Сложность и реальные вычисления», 1998
2. Клаус Вейраух, « Вычислительный анализ, введение », 2000

Прежде всего, вычислительные геометры не думают об этом как модель BSS. Модель реального ОЗУ была определена Майклом Шамосом в его докторской диссертации 1978 года ( Вычислительная геометрия ), которая, возможно, положила начало этой области. Франко Препарата пересмотрел и расширил тезис Шамоса в первом учебнике по вычислительной геометрии, опубликованном в 1985 году. Реальное ОЗУ также эквивалентно ( за исключением единообразия; см. Ответ Паскаля! ) Модели алгебраического дерева вычислений, определенной Бен-Ором в 1983 году. Блум Усилия Шуба и Смейла были опубликованы в 1989 году, задолго до того, как было создано реальное ОЗУ, и почти полностью игнорировались сообществом вычислительной геометрии.

Большинство (классических) результатов в вычислительной геометрии тесно связаны с проблемами комбинаторной геометрии, для которых предположения о том, что координаты являются интегральными или алгебраическими, в лучшем случае не имеют значения. Говоря как нативный, кажется совершенно естественным рассматривать произвольные точки, линии, круги и тому подобное в качестве объектов первого класса при доказательстве чего-либо о них и, следовательно, одинаково естественно при разработке и анализе алгоритмов для вычисления с ними.

$p$$q$$q$$r$$q,r,s$$qr$$st$? Каждый из этих примитивов реализуется путем оценки знака полинома низкой степени во входных координатах. (Таким образом, эти алгоритмы могут быть описаны в более слабой алгебраической модели дерева решений .) Если входные координаты оказываются целыми числами, эти примитивы могут быть оценены точно только с постоянным увеличением точности, и, таким образом, время выполнения в реальной ОЗУ и Целочисленная оперативная память одинакова.

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

Таким образом, сообщество разработало разделение проблем между дизайном «реальных» геометрических алгоритмов и их практической реализацией; отсюда и разработка пакетов типа LEDA и CGAL. Даже для людей, работающих над точными вычислениями, существует различие между реальным алгоритмом, который использует точную реальную арифметику как часть базовой модели, и реализацией , которая вынуждена в силу не относящихся к иным причинам ограничений физических вычислительных устройств использовать дискретные вычисления.

$\times$

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

Итак, мой короткий, лично предвзятый ответ таков: TTE, теория предметной области, Ко-Фридман и другие модели «реалистичных» вычислений с действительными числами - все они решают проблемы, которые сообществу вычислительной геометрии в целом просто не интересны ,

Не совсем верно, что реальная модель RAM / BSS эквивалентна модели дерева алгебраических вычислений. Последнее является более мощным, потому что дерево глубины полинома может иметь экспоненциальный размер. Это дает много места для кодирования неоднородной информации. Например, Meyer auf der Heide показал, что алгебраические (даже линейные) деревья решений могут эффективно решать сложные задачи, такие как сумма подмножеств, но это (предположительно) невозможно в реальной модели RAM / BSS.

Вот комментарий к превосходному ответу Джеффа:

Понятия условия, аппроксимации и округления были предложены для решения проблемы сложности (комбинаторный или непрерывный) алгоритмов линейного программирования. Условие экземпляра задачи оценивает влияние малых возмущений входа на точность вывода. Понятие условия было впервые введено Аланом Тьюрингом. Джим Ренегар ввел понятие условия линейной программы.

Л. Блюм, Вычислительное над переАльсом: Где Тюринг встречает Ньютон, , УВЕДОМЛЕНИЯ АСУ, том 51, номер 9, (2004), 1024-1034

A. TURING, Ошибки округления в матричных процессах, Quart. J. Mech. Appl. Математика 1 (1948), 287–308

J. RENEGAR, Включение условных чисел в теорию сложности линейного программирования, SIAM J. Optim. 5 (1995), 506–524

F. CUCKER и J. PEÑA, Первично-двойной алгоритм для решения многогранных конических систем с помощью машины конечной точности, SIAM Journal of Optimization 12 (2002), 522–554.