Описательная теория сложности - Descriptive complexity theory

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

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

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

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

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

Смотрите также

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

Рекомендации

• Рональд Феджин, Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время. Сложность вычислений, изд. Р. Карп, SIAM-AMS Proceedings 7, pp. 27–41. 1974 г.
• Феджин, Рональд (1993). «Теория конечных моделей - личная перспектива». Теоретическая информатика. 116: 3–31. Дои:10.1016 / 0304-3975 (93) 90218-я.
• Иммерман, Нил (1983). «Языки, охватывающие классы сложности». Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '83. С. 347–354. Дои: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.

внешняя ссылка

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