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

«Описательная сложность» перенаправляется сюда. Для измерения сложности отдельного объекта см. Колмогоровская сложность.

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

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

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

• Логика первого порядка определяет класс FO, соответствующий AC⁰, языки, распознаваемые схемами полиномиального размера с ограниченной глубиной, которая равна языкам, распознаваемым параллельная машина с произвольным доступом в постоянное время.
• Логика первого порядка с коммутативом, переходное закрытие оператор добавил урожайность SL, что равно L, задачи, решаемые в логарифмическом пространстве.
• Логика первого порядка с переходное закрытие оператор дает NL, задачи, разрешимые в недетерминированном логарифмическом пространстве.
• При наличии линейного порядка логика первого порядка с наименьшая фиксированная точка оператор дает п, задачи, решаемые за детерминированное полиномиальное время.
• Экзистенциальная логика второго порядка дает НП.
• Универсальная логика второго порядка (исключая экзистенциальную квантификацию второго порядка) дает ко-NP.
• Второго порядка логика соответствует PH, как уже упоминалось выше.
• Логика второго порядка с переходное закрытие (коммутативный или нет) дает PSPACE, задачи, разрешимые в полиномиальном пространстве.
• Логика второго порядка с наименьшая фиксированная точка оператор дает EXPTIME, задачи, решаемые за экспоненциальное время.
• ${\displaystyle \exists {\color {Blue}{\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 (сложность)
• Спектр предложения

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

1. Лаури Хелла и Хосе Мария Турулл-Торрес (2006), «Вычисление запросов с логикой высшего порядка», Теоретическая информатика ((что в bibtex называется «числом») изд.), Эссекс, Великобритания: Elsevier Science Publishers Ltd., 355 (2): 197–214, Дои:10.1016 / j.tcs.2006.01.009, ISSN  0304-3975

• Рональд Феджин, Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время. Сложность вычислений, изд. Р. Карп, 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.

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

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