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

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

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

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

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

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

дальнейшее чтение

  • Шон Хедман, Первый курс логики: введение в теорию моделей, теорию доказательств, вычислимость и сложность , 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 .

Внешние ссылки