Сложность и реальные вычисления
Complexity and Real Computation — книга по теории вычислительной сложности реальных вычислений . Она изучает алгоритмы , входные и выходные данные которых являются действительными числами , используя машину Блюма–Шуба–Смейла в качестве модели вычислений . Например, эта теория способна ответить на вопрос, поставленный в 1991 году Роджером Пенроузом в «Новом разуме императора» : «вычислимо ли множество Мандельброта ?» [1]
Книга была написана Ленор Блюм , Фелипе Кукером , Майклом Шубом и Стивеном Смейлом с предисловием Ричарда М. Карпа и опубликована издательством Springer-Verlag в 1998 году (doi:10.1007/978-1-4612-0701-6, ISBN 0-387-98281-7 ). [2]
Цель
Стивен Вавасис замечает, что эта книга заполняет существенный пробел в литературе: хотя ученые-теоретики, работающие над дискретными алгоритмами, изучали модели вычислений и их влияние на сложность алгоритмов с 1970-х годов, исследователи численных алгоритмов в большинстве случаев не смогли определить свою модель вычислений, оставив свои результаты на шатком фундаменте. Помимо цели сделать этот аспект темы более обоснованным, книга также имеет цели представить новые результаты в теории сложности вычислений действительных чисел и собрать ранее известные результаты в этой теории. [3]
Темы
Введение к книге перепечатывает статью «Сложность и реальные вычисления: манифест», ранее опубликованную теми же авторами. Этот манифест объясняет, почему классические дискретные модели вычислений, такие как машина Тьюринга, неадекватны для изучения численных задач в таких областях, как научные вычисления и вычислительная геометрия , мотивируя более новую модель, изучаемую в книге. После этого книга делится на три части. [2]
Часть I книги устанавливает модели вычислений над любым кольцом , с единичной стоимостью за операцию кольца. Она предоставляет аналоги теории рекурсии и проблемы 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
- ^ abcdefg Меер, Клаус (1999), «Обзор сложности и реальных вычислений », Mathematical Reviews , MR 1479636
- ^ abcde Вавасис, Стивен А. (июнь 1999 г.), «Обзор сложности и реальных вычислений », SIAM Review , 41 (2): 407–409, JSTOR 2653097
- ^ abc Бах, Эрик (2001), «Обзор сложности и реальных вычислений », Дискретная динамика в природе и обществе , 6 : 145–146, doi : 10.1155/S1026022601000152
Внешние ссылки
- Сложность и реальные вычисления в интернет-архиве
