Теория описательной сложности

Описательная сложность - это раздел теории сложности вычислений и теории конечных моделей, которая характеризует классы сложности по типу логики, необходимой для выражения в них языков. Например, PH, объединение всех классов сложности в полиномиальной иерархии, в точности является классом языков, выражаемым с помощью операторов логики второго порядка. Эта связь между сложностью и логикой конечных структур позволяет легко переносить результаты из одной области в другую, облегчая использование новых методов доказательства и предоставляя дополнительные доказательства того, что основные классы сложности так или иначе «естественны» и не привязаны к конкретному абстрактные машины используются для их определения.

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

Первым основным результатом описательной сложности была теорема Феджина, продемонстрированная Рональдом Фейджином в 1974 году. Она установила, что NP является в точности множеством языков, выражаемых предложениями экзистенциальной логики второго порядка ; то есть логика второго порядка, исключающая универсальную количественную оценку отношений, функций и подмножеств. Многие другие классы позже были охарактеризованы таким образом, большинство из них Нил Иммерман :

• Логика первого порядка определяет класс FO, соответствующий AC, языки, распознаваемые схемами полиномиального размера с ограниченной глубиной, что эквивалентно языкам, распознаваемым параллельной машиной произвольного доступа за постоянное время.
• Логика первого порядка с коммутативным, добавленный оператор транзитивного замыкания дает SL, что равно L, проблемы, решаемые в логарифмическом пространстве.
• Логика первого порядка с транзитивным замыканием Оператор дает NL, проблемы, решаемые в недетерминированном логарифмическом пространстве.
• При наличии линейного порядка логика первого порядка с оператором наименьшей фиксированной точки дает P, проблемы, решаемые за детерминированное полиномиальное время.
• Экзистенциальная логика второго порядка дает NP.
• Универсальная логика второго порядка (исключая экзистенциальную квантификацию второго порядка) дает ко-NP.
• Второй порядок Логика r соответствует PH, как упомянуто выше.
• Логика второго порядка с транзитивным замыканием (коммутативным или нет) дает PSPACE, задачи, решаемые в полиномиальном пространстве.
• Логика второго порядка с оператором наименьшей фиксированной точки дает EXPTIME, проблемы, решаемые в экспоненциальном времени.
• $\exists \; HO\; i\; \{\backslash \; displaystyle\; \backslash \; exists\; \{\backslash \; color\; \{Blue\}\; \{\backslash \; mathsf\; \{HO\}\}\}\; ^\; \{i\}\}$, логика с квантификатором существования порядка i, за которым следует формула порядка $i\; -\; 1\; \{\backslash \; displaystyle\; i-1\}$равно $NTIME\; (exp\; 2\; i\; -\; 2\; \; (n\; O\; (1)))\; \{\backslash \; displaystyle\; \{\backslash \; color\; \{Blue\}\; \{\backslash \; mathsf\; \{NTIME\}\}\}\; (\backslash \; exp\; \_\; \{2\}\; ^\; \{i-2\}\; (n\; ^\; \{O\; (1)\}))\}$
• $HO\; ji\; =\; NTIME\; (exp\; 2\; i\; -\; 2\; \; (n\; O\; (1)))\; \Sigma \; j\; P\; \{\backslash \; displaystyle\; \{\backslash \; mathsf\; \{HO\}\}\; \_\; \{j\}\; ^\; \{i\}\; =\; \{\backslash \; color\; \{Blue\}\; \{\backslash \; mathsf\; \{NTIME\}\}\}\; (\backslash \; exp\; \_\; \{2\}\; ^\; \{i-\; 2\}\; (n\; ^\; \{O\; (1)\}))\; ^\; \{\backslash \; Sigma\; \_\; \{j\}\; ^\; \{\backslash \; mathsf\; \{P\}\}\}\}$
• HO равно ELEMENTARY

• SO (сложность)
• FO (сложность)
• Спектр предложения

• Ronald Fagin, Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время. Сложность вычислений / Под ред. Р. Карп, SIAM-AMS Proceedings 7, pp. 27–41. 1974.
• Феджин, Рональд (1993). «Теория конечных моделей - личная перспектива». Теоретическая информатика. 116 : 3–31. doi : 10.1016 / 0304-3975 (93) 90218-i.
• Иммерман, Нил (1983). «Языки, охватывающие классы сложности». Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '83. С. 347–354. doi : 10.1145 / 800061.808765. ISBN 0897910990.
• Иммерман, Нил (1999). Описательная сложность. Нью-Йорк: Springer-Verlag. С. 113–119. ISBN 0-387-98600-6..

• Шон Хедман, Первый курс логики: введение в теорию моделей, теорию доказательств, вычислимость и сложность, Оксфордский университет Press, 2004, ISBN 0-19-852981-3, раздел 10.3 является подходящим введением для студентов
• Grädel, Erich; Колайтис, Phokion G.; Либкин, Леонид; Маартен, Маркс; Спенсер, Джоэл ; Варди, Моше Ю. ; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения. Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.

• Страница описательной сложности Нила Иммермана, включая диаграмму