Описательная теория сложности

Раздел математической логики

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

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

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

Обстановка

Когда мы используем логический формализм для описания вычислительной задачи, входные данные представляют собой конечную структуру, а элементы этой структуры являются областью дискурса . Обычно входные данные представляют собой либо строку (битовую или по алфавиту), а элементы логической структуры представляют позиции строки, либо входные данные представляют собой граф, а элементы логической структуры представляют его вершины. Длина входных данных будет измеряться размером соответствующей структуры. Какой бы ни была структура, мы можем предположить, что существуют отношения, которые можно проверить, например, « истинно тогда и только тогда, когда есть ребро из x в y » (в случае, если структура является графом), или « истинно тогда и только тогда, когда n- я буква строки равна 1». Эти отношения являются предикатами для логической системы первого порядка. У нас также есть константы, которые являются специальными элементами соответствующей структуры, например, если мы хотим проверить достижимость в графе, нам придется выбрать две константы s (начало) и t (конец). ${\displaystyle E(x,y)}$ ${\displaystyle P(n)}$

В теории дескриптивной сложности мы часто предполагаем, что существует полный порядок над элементами и что мы можем проверять равенство между элементами. Это позволяет нам рассматривать элементы как числа: элемент x представляет число n тогда и только тогда, когда существуют элементы y с . Благодаря этому мы также можем иметь примитивный предикат «bit», где является истинным, если только k -й бит двоичного разложения x равен 1. (Мы можем заменить сложение и умножение тернарными отношениями, такими что является истинным, если и только тогда, когда и является истинным, если и только тогда, когда ). ${\displaystyle (n-1)}$ ${\displaystyle y<x}$ ${\displaystyle bit(x,k)}$ ${\displaystyle plus(x,y,z)}$ ${\displaystyle x+y=z}$ ${\displaystyle times(x,y,z)}$ ${\displaystyle x*y=z}$

Обзор характеристик классов сложности

Если ограничиться упорядоченными структурами с отношением преемственности и базовыми арифметическими предикатами, то получим следующие характеристики:

• Логика первого порядка определяет класс AC 0 , языки, распознаваемые схемами полиномиального размера ограниченной глубины, что соответствует языкам, распознаваемым параллельной машиной с произвольным доступом за постоянное время. ^[1]
• Логика первого порядка, дополненная симметричными или детерминированными транзитивными операторами замыкания, дает L , задачи, разрешимые в логарифмическом пространстве. ^[2]
• Логика первого порядка с транзитивным оператором замыкания дает NL , задачи, разрешимые в недетерминированном логарифмическом пространстве. ^[3]
• Логика первого порядка с оператором наименьшей фиксированной точки дает P , задачи, решаемые за детерминированное полиномиальное время. ^[3]
• Экзистенциальная логика второго порядка дает NP . ^[3]
• Универсальная логика второго порядка (исключая экзистенциальную квантификацию второго порядка) дает co-NP . ^[4]
• Логика второго порядка соответствует полиномиальной иерархии PH . ^[3]
• Логика второго порядка с транзитивным замыканием (коммутативным или нет) дает PSPACE , задачи, решаемые в полиномиальном пространстве. ^[5]
• Логика второго порядка с оператором наименьшей фиксированной точки дает EXPTIME , задачи, решаемые за экспоненциальное время. ^[6]
• HO , класс сложности, определяемый логикой высшего порядка , равен ЭЛЕМЕНТАРНОМУ ^[7]

Субполиномиальное время

FO без операторов

В сложности схемы можно показать, что логика первого порядка с произвольными предикатами равна AC 0 , первому классу в иерархии AC . Действительно, существует естественный перевод из символов FO в узлы схем, причем и размера n . Логика первого порядка в сигнатуре с арифметическими предикатами характеризует ограничение семейства схем AC ^{0 теми, которые можно построить за} чередующееся логарифмическое время . ^[1] Логика первого порядка в сигнатуре только с отношением порядка соответствует множеству языков без звезд . ^{[8] [9]} ${\displaystyle \forall ,\exists }$ ${\displaystyle \land }$ ${\displaystyle \lor }$

Логика транзитивного замыкания

Логика первого порядка существенно выигрывает в выразительной силе, когда она дополняется оператором, который вычисляет транзитивное замыкание бинарного отношения. Известно, что полученная логика транзитивного замыкания характеризует недетерминированное логарифмическое пространство (NL) на упорядоченных структурах. Это использовал Иммерман, чтобы показать, что NL замкнуто относительно дополнения (т.е. что NL = co-NL). ^[10]

При ограничении оператора транзитивного замыкания до детерминированного транзитивного замыкания результирующая логика в точности характеризует логарифмическое пространство на упорядоченных структурах.

Формулы Крома второго порядка

На структурах, имеющих функцию преемника, NL также можно охарактеризовать с помощью формул Крома второго порядка .

SO-Krom — это набор булевых запросов, определяемых формулами второго порядка в конъюнктивной нормальной форме, такими, что квантификаторы первого порядка являются универсальными, а часть формулы без квантификаторов находится в форме Krom, что означает, что формула первого порядка является конъюнкцией дизъюнкций, и в каждой «дизъюнкции» содержится не более двух переменных. Каждая формула Krom второго порядка эквивалентна экзистенциальной формуле Krom второго порядка.

SO-Krom характеризует NL на структурах с функцией преемника. ^[11]

Полиномиальное время

В упорядоченных структурах логика наименьшего числа фиксированной точки первого порядка фиксирует PTIME :

Логика первого порядка с наименьшей фиксированной точкой

FO[LFP] — это расширение логики первого порядка оператором наименьшей фиксированной точки, который выражает фиксированную точку монотонного выражения. Это дополняет логику первого порядка способностью выражать рекурсию. Теорема Иммермана–Варди, показанная независимо Иммерманом и Варди , показывает, что FO[LFP] характеризует PTIME на упорядоченных структурах. ^{[12] [13]}

По состоянию на 2022 год все еще остается открытым вопрос о том, существует ли естественная логика, характеризующая PTIME на неупорядоченных структурах.

Теорема Абитбула–Виану утверждает, что FO[LFP]=FO[PFP] для всех структур тогда и только тогда, когда FO[LFP]=FO[PFP]; следовательно, тогда и только тогда, когда P=PSPACE. Этот результат был распространен на другие неподвижные точки. ^[14]

Формулы Хорна второго порядка

При наличии функции-последователя PTIME также может быть охарактеризована формулами Хорна второго порядка.

SO-Horn — это набор булевых запросов, определяемых с помощью формул SO в дизъюнктной нормальной форме, таких, что все квантификаторы первого порядка являются универсальными, а часть формулы, не содержащая квантификаторов, находится в форме Хорна , что означает, что это большое И или ИЛИ, и в каждом «ИЛИ» все переменные, за исключением, возможно, одной, отрицаются.

Этот класс равен P на структурах с функцией преемника. ^[15]

Эти формулы можно преобразовать в предваренные формулы в экзистенциальной логике второго порядка Хорна. ^[11]

Недетерминированное полиномиальное время

Теорема Фейгина

Доказательство Рональда Фейгина 1974 года о том, что класс сложности NP характеризуется именно теми классами структур, которые аксиоматизируются в экзистенциальной логике второго порядка, стало отправной точкой дескриптивной теории сложности. ^{[4] [16]}

Поскольку дополнение экзистенциальной формулы является универсальной формулой, то отсюда немедленно следует, что co-NP характеризуется универсальной логикой второго порядка. ^[4]

SO, неограниченная логика второго порядка, эквивалентна полиномиальной иерархии PH . Точнее, мы имеем следующее обобщение теоремы Фейгина: множество формул в предваренной нормальной форме, где кванторы существования и всеобщности второго порядка чередуются k раз, характеризуют k -й уровень полиномиальной иерархии. ^[17]

В отличие от большинства других характеристик классов сложности, теорема Фейгина и ее обобщение не предполагают полного упорядочения структур. Это происходит потому, что экзистенциальная логика второго порядка сама по себе достаточно выразительна, чтобы ссылаться на возможные полные порядки структуры, используя переменные второго порядка. ^[18]

За пределами НП

Частичная фиксированная точка — PSPACE

Класс всех задач, вычислимых в полиномиальном пространстве, PSPACE , можно охарактеризовать, дополнив логику первого порядка более выразительным частичным оператором с фиксированной точкой.

Частичная логика с фиксированной точкой , FO[PFP], является расширением логики первого порядка с помощью частичного оператора с фиксированной точкой, который выражает фиксированную точку формулы, если таковая имеется, и возвращает «ложь» в противном случае.

Частичная логика с фиксированной точкой характеризует PSPACE на упорядоченных структурах. ^[19]

Транзитивное замыкание — PSPACE

Логика второго порядка может быть расширена транзитивным оператором замыкания таким же образом, как и логика первого порядка, что приводит к SO[TC]. Оператор TC теперь может также принимать переменные второго порядка в качестве аргумента. SO[TC] характеризует PSPACE . Поскольку на порядок можно ссылаться в логике второго порядка, эта характеристика не предполагает упорядоченных структур. ^[20]

Элементарные функции

Класс сложности по времени ELEMENTARY элементарных функций можно охарактеризовать с помощью HO , класса сложности структур, которые могут быть распознаны формулами логики высшего порядка . Логика высшего порядка является расширением логики первого порядка и логики второго порядка с кванторами высшего порядка. Существует связь между порядком th и недетерминированными алгоритмами, время которых ограничено уровнями экспонент. ^[21] ${\displaystyle i}$ ${\displaystyle i-1}$

Определение

Мы определяем переменные высшего порядка. Переменная порядка имеет арность и представляет собой любой набор из - кортежей элементов порядка . Обычно они пишутся заглавными буквами и с натуральным числом в качестве показателя степени для указания порядка. Логика высшего порядка - это набор формул первого порядка, в которые мы добавляем квантификацию по переменным высшего порядка; поэтому мы будем использовать термины, определенные в статье FO , не определяя их снова. ${\displaystyle i>1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle i-1}$

HO — это множество формул с переменными порядка не более . HO — это подмножество формул вида , где — квантификатор, а означает, что — кортеж переменных порядка с той же квантификацией. Таким образом, HO — это множество формул с чередованием квантификаторов порядка , начинающихся с , за которыми следует формула порядка . ${\displaystyle ^{i}}$ ${\displaystyle i}$ ${\displaystyle _{j}^{i}}$ ${\displaystyle \phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi }$ ${\displaystyle Q}$ ${\displaystyle Q{\overline {X^{i}}}}$ ${\displaystyle {\overline {X^{i}}}}$ ${\displaystyle i}$ ${\displaystyle _{j}^{i}}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle \exists }$ ${\displaystyle i-1}$

Используя стандартную запись тетрации , и . со временем ${\displaystyle \exp _{2}^{0}(x)=x}$ ${\displaystyle \exp _{2}^{i+1}(x)=2^{\exp _{2}^{i}(x)}}$ ${\displaystyle \exp _{2}^{i+1}(x)=2^{2^{2^{2^{\dots ^{2^{x}}}}}}}$ ${\displaystyle i}$ ${\displaystyle 2}$

Нормальная форма

Каждая формула порядка th эквивалентна формуле в предваренной нормальной форме, где сначала мы записываем квантификацию по переменной порядка th, а затем формулу порядка в нормальной форме. ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i-1}$

Отношение к классам сложности

HO равно классу ELEMENTARY элементарных функций. Точнее, , что означает башню из двоек, заканчивающуюся на , где — константа. Частным случаем этого является , что в точности соответствует теореме Фейгина . Использование машин-оракулов в полиномиальной иерархии , ${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$ ${\displaystyle (i-2)}$ ${\displaystyle n^{c}}$ ${\displaystyle c}$ ${\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}$ ${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}$

Примечания

1. Immerman 1999, стр. 86
2. Гредель, Эрих; Шальтёфер, Свенья (2019). Безвыборное логарифмическое пространство. Международные труды Лейбница по информатике (LIPIcs). Том. 138. стр. 31:1–31:15. doi : 10.4230/LIPICS.MFCS.2019.31 . ISBN 9783959771177.
3. Иммерман 1999, стр. 242
4. Фагин, Рон (1974). «Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время». В Карпе, Ричарде (ред.). Сложность вычислений . стр. 43–73.
5. Иммерман 1999, стр. 243
6. Абитбуль, Серж; Варди, Моше Й.; Виану, Виктор (1997-01-15). «Логика неподвижной точки, реляционные машины и вычислительная сложность». Журнал ACM . 44 (1): 30–56. doi : 10.1145/256292.256295 . ISSN  0004-5411. S2CID  11338470.
7. Хелла, Лаури; Турулл-Торрес, Хосе Мария (2006). «Вычислительные запросы с логикой высшего порядка». Теоретическая информатика . 355 (2). Эссекс, Великобритания: Elsevier Science Publishers Ltd.: 197–214. doi : 10.1016/j.tcs.2006.01.009 . ISSN  0304-3975.
8. Роберт., Макнотон (1971). Автоматы без счетчиков. MIT Press. ISBN 0-262-13076-9. OCLC  651199926.
9. Иммерман 1999, стр. 22
10. Иммерман, Нил (1988). «Недетерминированное пространство замкнуто при дополнении». Журнал SIAM по вычислениям . 17 (5): 935–938. doi :10.1137/0217058. ISSN  0097-5397.
11. Иммерман 1999, с. 153–4
12. Иммерман, Нил (1986). «Реляционные запросы, вычислимые за полиномиальное время». Информация и управление . 68 (1–3): 86–104. doi : 10.1016/s0019-9958(86)80029-8 .
13. Варди, Моше Й. (1982). «Сложность реляционных языков запросов (Расширенный реферат)». Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 . Нью-Йорк, Нью-Йорк, США: ACM. стр. 137–146. CiteSeerX 10.1.1.331.6045 . doi :10.1145/800070.802186. ISBN  978-0897910705. S2CID  7869248.
14. Серж Абитбуль, Моше И. Варди , Виктор Виану : Логика фиксированной точки, реляционные машины и вычислительная сложность Журнал архива ACM, том 44, выпуск 1 (январь 1997 г.), страницы: 30-56, ISSN  0004-5411
15. Грэдель, Эрих (1992-07-13). «Охват классов сложности фрагментами логики второго порядка». Теоретическая информатика . 101 (1): 35–57. doi : 10.1016/0304-3975(92)90149-A . ISSN  0304-3975.
16. Иммерман 1999, стр. 115
17. Иммерман 1999, стр. 121
18. Иммерман 1999, стр. 181
19. Abiteboul, S.; Vianu, V. (1989). "Расширения фиксированной точки логики первого порядка и языки, подобные языкам datalog". [1989] Труды. Четвертый ежегодный симпозиум по логике в информатике . IEEE Comput. Soc. Press. стр. 71–79. doi :10.1109/lics.1989.39160. ISBN 0-8186-1954-6. S2CID  206437693.
20. Харель, Д.; Пелег, Д. (1984-01-01). «О статических логиках, динамических логиках и классах сложности». Информация и управление . 60 (1): 86–102. doi : 10.1016/S0019-9958(84)80023-6 . ISSN  0019-9958.
21. Хелла, Лаури; Турулл-Торрес, Хосе Мария (2006). «Вычислительные запросы с логикой высшего порядка». Теоретическая информатика . 355 (2). Эссекс, Великобритания: Elsevier Science Publishers Ltd.: 197–214. doi : 10.1016/j.tcs.2006.01.009 . ISSN  0304-3975.

Ссылки

• Иммерман, Нил (1999). Описательная сложность. Springer. ISBN 0-387-98600-6. OCLC  901297152.

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

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