Сложность и реальные вычисления
«Сложность и реальные вычисления» — книга по теории вычислительной сложности реальных вычислений . Он изучает алгоритмы, входными и выходными данными которых являются действительные числа , используя машину Блюма-Шаба-Смейла в качестве модели вычислений . Например, эта теория способна ответить на вопрос, поставленный в 1991 году Роджером Пенроузом в книге «Новый разум императора» : «вычислимо ли множество Мандельброта ?» [1]
Книга была написана Ленорой Блюм , Фелипе Какером , Майклом Шабом и Стивеном Смейлом , с предисловием Ричарда М. Карпа и опубликована издательством Springer-Verlag в 1998 году ( doi:10.1007/978-1-4612-0701-6 , ISBN 0-387-98281-7 ). [2]
Цель
[ редактировать ]Стивен Вавасис отмечает, что эта книга заполняет значительный пробел в литературе: хотя ученые-теоретики, работающие над дискретными алгоритмами, изучали модели вычислений и их влияние на сложность алгоритмов с 1970-х годов, исследователи численных алгоритмов по большей части потерпели неудачу. определить свою модель вычислений, оставив результаты на шатком фундаменте. Помимо цели сделать этот аспект темы более обоснованным, цель книги также состоит в том, чтобы представить новые результаты в теории сложности вычислений действительных чисел и собрать ранее известные результаты в этой теории. [3]
Темы
[ редактировать ]Введение к книге перепечатывает статью «Сложность и реальные вычисления: манифест», ранее опубликованную теми же авторами. Этот манифест объясняет, почему классические дискретные модели вычислений, такие как машина Тьюринга, не подходят для изучения численных проблем в таких областях, как научные вычисления и вычислительная геометрия , что мотивирует создание новой модели, изучаемой в книге. После этого книга разделена на три части. [2]
В первой части книги представлены модели вычислений над любым кольцом с удельной стоимостью операции в кольце. Он предоставляет аналоги теории рекурсии и проблемы P и NP в каждом случае и доказывает существование NP-полных задач аналогично доказательству теоремы Кука – Левина в классической модели, которую можно рассматривать как частный случай эта теория для арифметики по модулю 2 . кольцо целых чисел В качестве частного примера изучается , а также алгебраически замкнутые поля , нулевой характеристики которые с точки зрения NP-полноты в рамках своих вычислительных моделей все эквивалентны комплексным числам . [2] ( Эрик Бах указывает, что эту эквивалентность можно рассматривать как форму принципа Лефшеца .) [4]
Часть II посвящена алгоритмам численной аппроксимации, использованию метода Ньютона для этих алгоритмов, а также альфа-теории автора Стивена Смейла для численной сертификации точности результатов этих вычислений. включают поиск корней многочленов Другие темы, рассматриваемые в этом разделе , и точек пересечения алгебраических кривых , число обусловленности систем уравнений и временную сложность линейного программирования с рациональными коэффициентами. [2]
В части III представлены аналоги теории структурной сложности и описательной теории сложности для вычислений с действительными числами, включая множество разделений классов сложности, которые доказуемы в этой теории, хотя аналогичные разделения в классической теории сложности остаются недоказанными. Ключевым инструментом в этой области является использование количества связных компонентов полуалгебраического набора для определения нижней границы временной сложности соответствующей вычислительной задачи. [2]
Аудитория и прием
[ редактировать ]Книга рассчитана на уровень аспиранта или исследователя по данной тематике, [2] [3] а местами это предполагает базовые знания классической теории сложности вычислений, дифференциальной геометрии , топологии и динамических систем . [3] [4]
Рецензент Клаус Меер пишет, что книга «очень хорошо написана», «идеально подходит для использования на уровне выпускников» и хорошо отражает как современное состояние в этой области, так и прочные связи, которые можно установить между такими разнообразными областями, как алгебраическая теория чисел , алгебраическая геометрия , математическая логика и численный анализ . [2]
В качестве незначительной критики, направленной больше на модель Блюма-Шаба-Смейла, чем на книгу, Стивен Вавасис отмечает, что (в отличие от машин Тьюринга) кажущиеся незначительными детали в модели, такие как способность вычислять функции пола и потолка , могут имеют большое значение в том, что можно вычислить и насколько эффективно это можно вычислить. Однако, пишет Вавасис, «эта трудность, вероятно, присуща самой теме». [3] В связи с этим Эрик Бах жалуется, что присвоение стоимости единицы всем арифметическим операциям может дать неверное представление о сложности задачи при практических вычислениях. [4] и Вавасис также отмечает, что на момент публикации его обзора эта работа, по-видимому, мало повлияла на практические исследования в области научных вычислений . Несмотря на эти проблемы, он рекомендует книгу как удобный и ясно написанный сборник теории численных вычислений. [3]
Ссылки
[ редактировать ]- ^ МакНиколл, Тимоти Х. (июнь 2001 г.), «Обзор сложности и реальных вычислений », SIGACT News , 32 (2): 14–15, doi : 10.1145/504192.1005765
- ^ Jump up to: а б с д и ж г Меер, Клаус (1999), «Обзор сложности и реальных вычислений », Mathematical Reviews , MR 1479636
- ^ Jump up to: а б с д и Вавасис, Стивен А. (июнь 1999 г.), «Обзор сложности и реальных вычислений », SIAM Review , 41 (2): 407–409, JSTOR 2653097
- ^ Jump up to: а б с Бах, Эрик (2001), «Обзор сложности и реальных вычислений », Дискретная динамика в природе и обществе , 6 : 145–146, doi : 10.1155/S1026022601000152