Описательная Сложность книга в математической логике и теории сложности вычислений по Neil Иммерман . Это касается описательной теории сложности , области, в которой выражаемость математических свойств с использованием различных типов логики эквивалентна их вычислимости в различных типах моделей вычислений с ограниченными ресурсами. Он был опубликован в 1999 году компанией Springer-Verlag в их серии книг «Тексты для выпускников в области компьютерных наук».
Темы
В книге 15 глав, которые примерно сгруппированы в пять глав по логике первого порядка , три по логике второго порядка и семь независимых глав по продвинутым темам. [1] [2]
Первые две главы предоставляют справочный материал по логике первого порядка (включая арифметику первого порядка , предикат BIT и понятие запроса первого порядка) и теории сложности (включая формальные языки , классы сложности с ограниченными ресурсами и полные задачи. ). В третьей главе начинается связь между логикой и сложностью, с доказательства того, что распознаваемые в первом порядке языки могут быть распознаны в логарифмическом пространстве , а также с построения полных языков для логарифмического пространства, недетерминированного логарифмического пространства и полиномиального времени . Четвертая глава посвящена индуктивным определениям, операторам с фиксированной точкой и описанию полиномиального времени в терминах логики первого порядка с оператором с наименьшей фиксированной точкой. Часть книги, посвященная темам первого порядка, заканчивается главой, посвященной логическим характеристикам границ ресурсов для параллельных машин с произвольным доступом и сложности схем . [1] [2] [3]
В шестой главе представлены игры Эренфойхта – Фраисе , ключевой инструмент доказательства логической невыразимости, а в седьмой главе представлена логика второго порядка. Он включает теорему Феджина, характеризующую недетерминированное полиномиальное время в терминах экзистенциальной логики второго порядка, теорему Кука – Левина о существовании NP-полных проблем и расширения этих результатов на полиномиальную иерархию . В восьмой главе игры используются для доказательства невыразимости некоторых языков в логике второго порядка. [1] [2] [3]
Глава девятая касается дополнения языков и оператора транзитивного замыкания , включая теорему Иммермана – Селепсеньи о том, что недетерминированное логарифмическое пространство замкнуто относительно дополнения. В десятой главе представлены полные задачи и дана логическая характеристика второго порядка полиномиального пространства . Глава одиннадцатая касается единообразия сложности схем (различие между существованием схем для решения проблемы и их алгоритмической конструктивностью), а глава двенадцатая касается роли упорядочивания и подсчета предикатов в логических характеристиках классов сложности. В тринадцатой главе используется лемма о переключении для нижних оценок, а в четырнадцатой главе речь идет о приложениях к базам данных и проверке моделей . В последней главе излагаются темы, по-прежнему нуждающиеся в исследованиях в этой области. [1] [2] [3]
Аудитория и прием
Книга в первую очередь предназначена для исследователей в этой области [1], но ее также можно использовать в качестве основы для аспирантуры и для этой цели есть упражнения. Хотя он утверждает, что он самодостаточен, рецензент В. Клоновски пишет, что его читатели должны уже понимать как классическую сложность, так и основы математической логики. [2]
Рецензент Анудж Давар пишет, что некоторые из первых обещаний описательной сложности были ослаблены его неспособностью использовать логические инструменты для решения основных проблем теории сложности, а также необходимостью добавления подобных вычислений дополнений к логическим языкам для использования их для характеристики вычислений. Тем не менее, пишет он, книга полезна как способ познакомить исследователей с этим направлением исследований и с менее изученным способом приближения к вычислительной сложности. [4]
Рекомендации
- ^ Б с д е Lindell, Стивен (декабрь 2001), "Обзор описательной сложности ", Бюллетень символической логики , 7 (4): 525-527, DOI : 10,2307 / 2687799 , JSTOR 2687799
- ^ а б в г д Klonowski, W. (2001), "Обзор описательной сложности ", дискретная динамика в природе и обществе , 6 : 57-62, DOI : 10,1155 / S1026022601000061
- ^ а б в Шёнинг, Уве , "Обзор описательной сложности ", zbMATH , Zbl 0918.68031
- ^ Давар, Анудж (2001), "Обзор описательной сложности ", Mathematical Reviews , MR 1732784