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

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

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

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

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

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

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

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