Описательная сложность - это раздел теории сложности вычислений и теории конечных моделей, который характеризует классы сложности по типу логики, необходимой для выражения в них языков. Например, PH , объединение всех классов сложности в полиномиальной иерархии, является в точности классом языков, выражаемых с помощью утверждений логики второго порядка . Эта связь между сложностью и логикой конечных структур позволяет легко переносить результаты из одной области в другую, облегчая использование новых методов доказательства и предоставляя дополнительные доказательства того, что основные классы сложности так или иначе «естественны» и не привязаны к конкретным условиям.абстрактные машины, используемые для их определения.
В частности, каждая логическая система производит набор запросов, выражаемых в ней. Запросы - если они ограничены конечными структурами - соответствуют вычислительным задачам традиционной теории сложности.
Первым основным результатом описательной сложности была теорема Феджина , показанная Рональдом Фейджином в 1974 году. Она установила, что NP - это в точности набор языков, выражаемых предложениями экзистенциальной логики второго порядка ; то есть логика второго порядка, исключающая универсальную количественную оценку отношений, функций и подмножеств. Многие другие классы позже были охарактеризованы таким образом, большинство из них Нил Иммерман :
- Логика первого порядка определяет класс FO , соответствующий AC 0 , языкам, распознаваемым схемами полиномиального размера с ограниченной глубиной, что соответствует языкам, распознаваемым параллельной машиной произвольного доступа в постоянное время.
- Логика первого порядка с добавленным коммутативным транзитивным оператором замыкания дает SL , который равен L , проблемы, решаемые в логарифмическом пространстве.
- Логика первого порядка с оператором транзитивного замыкания дает NL , задачи, разрешимые в недетерминированном логарифмическом пространстве.
- При наличии линейного порядка логика первого порядка с оператором с наименьшей фиксированной точкой дает P - задачи, решаемые за детерминированное полиномиальное время.
- Экзистенциальная логика второго порядка дает NP .
- Универсальная логика второго порядка (исключая экзистенциальную количественную оценку второго порядка) дает ко-NP.
- Как упоминалось выше, логика второго порядка соответствует PH .
- Логика второго порядка с транзитивным замыканием (коммутативным или нет) дает PSPACE , проблемы, разрешимые в полиномиальном пространстве.
- Логика второго порядка с оператором наименьшей фиксированной точки дает EXPTIME , проблемы, решаемые за экспоненциальное время.
- , логика с экзистенциальным квантором порядка i, за которым следует формула порядка равно [1]
- HO невероятно похож на ELEMENTARY
Смотрите также
Рекомендации
- ^ Лаури Hella и Хосе Мария Turull-Торрес (2006), "Вычислительные запросы с логик более высокого порядка" , Теоретическая информатика ((что называется "номер" в BibTex) под ред.), Эссекс, Великобритания: Elsevier Science Publishers Ltd. , 355 (2): 197-214, DOI : 10.1016 / j.tcs.2006.01.009 , ISSN 0304-3975
- Рональд Фэджин , Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время . Сложность вычислений / Под ред. Р. Карп, 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 .
Внешние ссылки
- Страница описательной сложности Нила Иммермана , включая диаграмму