Сложность и реальные вычисления - 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 в каждом случае и доказывает существование НП-полный проблемы аналогично доказательству Теорема Кука – Левина в классической модели, которую можно рассматривать как частный случай этой теории для арифметика по модулю 2. Кольцо целые числа исследуется как частный пример, как и алгебраически замкнутые поля из характеристика ноль, которые показаны с точки зрения NP-полноты в рамках своих вычислительных моделей, чтобы все они были эквивалентны сложные числа.[2] (Эрик Бах указывает, что эту эквивалентность можно рассматривать как форму Принцип Лефшеца.)[4]

Часть II посвящена алгоритмам численной аппроксимации, использованию Метод Ньютона для этих алгоритмов и на альфа-теорию автора Стивена Смейла для цифровая аттестация точности результатов этих вычислений. Другие темы, рассматриваемые в этом разделе, включают поиск корни из многочлены и точки пересечения алгебраические кривые, то номер условия систем уравнений, а временная сложность линейное программирование с участием рациональный коэффициенты.[2]

В части III представлены аналоги теория структурной сложности и описательная теория сложности для вычислений с действительными числами, включая многие разделения классов сложности, которые доказуемы в этой теории, даже если аналогичные разделения в классической теории сложности остаются недоказанными. Ключевым инструментом в этой области является использование количества связанных компонентов полуалгебраическое множество для обеспечения нижней границы временной сложности связанной вычислительной задачи.[2]

Аудитория и прием

Книга ориентирована на уровень аспиранта или исследователя в этих темах,[2][3] а местами предполагает наличие базовых знаний классической теории сложности вычислений, дифференциальная геометрия, топология, и динамические системы.[3][4]

Рецензент Клаус Меер пишет, что книга «очень хорошо написана», «идеально подходит для использования на уровне выпускников» и хорошо представляет как современное состояние в этой области, так и тесные связи, которые могут быть установлены между такими разными областями, как алгебраическая теория чисел, алгебраическая геометрия, математическая логика, и численный анализ.[2]

В качестве незначительной критики, направленной больше на модель Блюма – Шуба – Смейла, чем на книгу, Стивен Вавасис отмечает, что (в отличие от машин Тьюринга), казалось бы, незначительные детали в модели, такие как способность вычислять функции пола и потолка, может существенно повлиять на то, что вычислимо и насколько эффективно это можно вычислить. Однако, пишет Вавасис, «эта трудность, вероятно, заложена в теме».[3] Соответственно, Эрик Бах жалуется, что присвоение стоимости единицы всем арифметическим операциям может дать неверное представление о сложности задачи в практических вычислениях,[4] и Вавасис также отмечает, что на момент публикации его обзора эта работа, по-видимому, мало повлияла на практические исследования в научные вычисления. Несмотря на эти проблемы, он рекомендует книгу как удобный и четко написанный сборник теории численных вычислений.[3]

использованная литература

  1. ^ Макниколл, Тимоти Х. (июнь 2001 г.), "Обзор Сложность и реальные вычисления", Новости SIGACT, 32 (2): 14–15, Дои:10.1145/504192.1005765
  2. ^ а б c d е ж г Меер, Клаус (1999), "Обзор Сложность и реальные вычисления", Математические обзоры, Г-Н  1479636
  3. ^ а б c d е Вавасис, Стивен А. (июнь 1999 г.), "Обзор Сложность и реальные вычисления", SIAM Обзор, 41 (2): 407–409, JSTOR  2653097
  4. ^ а б c Бах, Эрик (2001), "Обзор Сложность и реальные вычисления", Дискретная динамика в природе и обществе, 6: 145–146, Дои:10.1155 / S1026022601000152

внешние ссылки