Теория описательной сложности - Descriptive complexity theory
Описательная сложность представляет собой ветвь теории сложности вычислений и теории конечных моделей , которая характеризует классы сложностей по типу логики , необходимого для выражения языка в них. Например, PH , объединение всех классов сложности в полиномиальной иерархии, является в точности классом языков, выражаемых с помощью утверждений логики второго порядка . Эта связь между сложностью и логикой конечных структур позволяет легко переносить результаты из одной области в другую, облегчая использование новых методов доказательства и предоставляя дополнительные доказательства того, что основные классы сложности так или иначе «естественны» и не привязаны к конкретным используемым абстрактным машинам. чтобы определить их.
В частности, каждая логическая система производит набор запросов, выражаемых в ней. Запросы - если они ограничены конечными структурами - соответствуют вычислительным задачам традиционной теории сложности.
Первым основным результатом описательной сложности была теорема Феджина , показанная Рональдом Фейджином в 1974 году. Она установила, что NP - это в точности набор языков, выражаемых предложениями экзистенциальной логики второго порядка ; то есть логика второго порядка, исключающая универсальную количественную оценку отношений, функций и подмножеств. Многие другие классы позже были охарактеризованы таким образом, большинство из них Нил Иммерман :
- Логика первого порядка определяет класс FO , соответствующий AC 0 , языкам, распознаваемым схемами полиномиального размера с ограниченной глубиной, что соответствует языкам, распознаваемым параллельной машиной произвольного доступа в постоянное время.
- Логика первого порядка с добавленным коммутативным транзитивным оператором замыкания приводит к SL , который равен L , задачам, решаемым в логарифмическом пространстве.
- Логика первого порядка с оператором транзитивного замыкания дает NL , задачи, разрешимые в недетерминированном логарифмическом пространстве.
- При наличии линейного порядка логика первого порядка с оператором с наименьшей фиксированной точкой дает P - задачи, решаемые за детерминированное полиномиальное время.
- Экзистенциальная логика второго порядка дает NP .
- Универсальная логика второго порядка (исключая экзистенциальную количественную оценку второго порядка) дает ко-NP.
- Как упоминалось выше, логика второго порядка соответствует PH .
- Логика второго порядка с транзитивным замыканием (коммутативным или нет) дает PSPACE , проблемы, разрешимые в полиномиальном пространстве.
- Логика второго порядка с оператором наименьшей фиксированной точки дает EXPTIME , проблемы, решаемые за экспоненциальное время.
- , логика с квантором существования порядка i, за которым следует формула порядка , равна
- HO невероятно похож на ELEMENTARY
Смотрите также
Рекомендации
- Рональд Фэджин , Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время . Сложность вычислений / Под ред. Р. Карп, SIAM-AMS Proceedings 7, pp. 27–41. 1974 г.
- Феджин, Рональд (1993). «Теория конечных моделей - личная перспектива» . Теоретическая информатика . 116 : 3–31. DOI : 10.1016 / 0304-3975 (93) 90218-я .
- Иммерман, Нил (1983). «Языки, охватывающие классы сложности». Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '83 . С. 347–354. DOI : 10.1145 / 800061.808765 . ISBN 0897910990.
- Иммерман, Нил (1999). Описательная сложность . Нью-Йорк: Springer-Verlag. С. 113–119. ISBN 0-387-98600-6..
дальнейшее чтение
- Шон Хедман, Первый курс логики: введение в теорию моделей, теорию доказательств, вычислимость и сложность , Oxford University Press, 2004, ISBN 0-19-852981-3 , раздел 10.3 - подходящее введение для студентов.
- Грэдель, Эрих; Колайтис, Phokion G .; Либкин, Леонид; Маартен, Маркс; Спенсер, Джоэл ; Варди, Моше Ю .; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN 978-3-540-00428-8. Zbl 1133.03001 .
Внешние ссылки
- Страница описательной сложности Нила Иммермана , включая диаграмму