Описательная сложность

Эта статья о книге. Информацию о теории см. в разделе «Описательная теория сложности» .

«Описательная сложность» — книга Нила Иммермана по и теории сложности вычислений математической логике . Речь идет о описательной теории сложности — области, в которой доказано, что выражаемость математических свойств с использованием различных типов логики эквивалентна их вычислимости в различных типах моделей вычислений с ограниченными ресурсами. Он был опубликован в 1999 году издательством Springer-Verlag в серии книг «Тексты для выпускников по информатике».

Темы

В книге 15 глав, примерно сгруппированных в пять глав по логике первого порядка , три по логике второго порядка и семь независимых глав по более сложным темам.

Первые две главы содержат справочный материал по логике первого порядка (включая арифметику первого порядка , предикат BIT и понятие запроса первого порядка) и теории сложности (включая формальные языки с ограниченными ресурсами , классы сложности и полные задачи). ). Глава третья начинается с связи между логикой и сложностью, с доказательства того, что распознаваемые языки первого порядка могут быть распознаны в логарифмическом пространстве , и построения полных языков для логарифмического пространства, недетерминированного логарифмического пространства и полиномиального времени . Четвертая глава посвящена индуктивным определениям, операторам с фиксированной точкой и характеристике полиномиального времени в терминах логики первого порядка с наименьшим оператором с фиксированной точкой. Часть книги, посвященная темам первого порядка, заканчивается главой, посвященной логическим характеристикам границ ресурсов для параллельных машин с произвольным доступом и сложности схем .

В шестой главе представлены игры Эренфойхта-Фрэссе , ключевой инструмент для доказательства логической невыразимости, а в седьмой главе представлена ​​логика второго порядка. Он включает в себя теорему Феджина, характеризующую недетерминированное полиномиальное время с точки зрения экзистенциальной логики второго порядка, теорему Кука-Левина о существовании NP-полных задач и распространение этих результатов на полиномиальную иерархию . В восьмой главе игры используются для доказательства невыразимости некоторых языков в логике второго порядка.

Глава девятая посвящена дополнению языков и оператору транзитивного замыкания , включая теорему Иммермана – Селепшени о том, что недетерминированное логарифмическое пространство замкнуто относительно дополнения. второго порядка В десятой главе представлены полные задачи и логическая характеристика полиномиального пространства . Глава одиннадцатая посвящена единообразию сложности схем (различие между существованием схем решения проблемы и их алгоритмической конструктивностью), а глава двенадцатая посвящена роли предикатов упорядочивания и подсчета в логических характеристиках классов сложности. В тринадцатой главе для нижних границ используется лемма переключения , а в четырнадцатой главе рассматриваются приложения к базам данных и проверке моделей . В последней главе излагаются темы, которые все еще нуждаются в исследованиях в этой области.

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

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

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