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

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

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

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

Обстановка

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

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

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

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

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

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

ФО без каких-либо операторов

По сложности схемы можно показать, что логика первого порядка с произвольными предикатами равна AC ⁰, первый класс в иерархии AC . Действительно, существует естественный перевод символов FO в узлы цепей, причем $\forall ,\exists$ существование $\land$ и $\lor$ размера $n$ . Логика первого порядка в сигнатуре с арифметическими предикатами характеризует ограничение АС ⁰ семейство схем к схемам, которые можно построить в попеременно-логарифмическом времени . ^[1] Логика первого порядка в сигнатуре, содержащей только отношение порядка, соответствует множеству бесзвездных языков . ^[8]^[9]

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

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

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

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

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

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

СО-кром характеризует НЛ на структурах с функцией-преемником. ^[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]

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

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

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

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

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

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

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

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

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

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

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

Класс временной сложности классом ЭЛЕМЕНТАРНО элементарных функций можно охарактеризовать НО , сложности структур, распознаваемых формулами логики высшего порядка . Логика высшего порядка является расширением логики первого порядка и логики второго порядка с помощью кванторов более высокого порядка. Существует связь между $i$ -го порядка и недетерминированные алгоритмы, время которых ограничено $i-1$ уровни экспонент. ^[21]

Определение

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

К $^{i}$ – совокупность формул с переменными порядка не выше $i$ . К $_{j}^{i}$ – подмножество формул вида $\phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi$ , где $Q$ является квантором и $Q{\overline {X^{i}}}$ означает, что ${\overline {X^{i}}}$ представляет собой кортеж переменной порядка $i$ с той же количественной оценкой. Итак, ХО $_{j}^{i}$ представляет собой набор формул с $j$ чередования кванторов порядка $i$ , начиная с $\exists$ , за которым следует формула порядка $i-1$ .

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

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

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

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

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

Примечания

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

Ссылки

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

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

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

[Immerman_1999,_p._86-1] Jump up to: ^а ^б Иммерман 1999, с. 86

[2] Гредель, Эрих; Шальтёфер, Свенья (2019). Логарифмическое пространство без выбора . Международные труды Лейбница по информатике (LIPIcs). Том 138. стр. 31: 1–31: 15. doi : 10.4230/LIPICS.MFCS.2019.31 . ISBN 9783959771177 .

[:0-3] Jump up to: ^а ^б ^с ^д Иммерман 1999, с. 242

[:1-4] Jump up to: ^а ^б ^с Феджин, Рон (1974). «Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время». В Карп, Ричард (ред.). Сложность вычислений . стр. 43–73.

[5] Иммерман 1999, с. 243

[6] Абитбул, Серж; Варди, Моше Ю.; Виану, Виктор (15 января 1997 г.). «Логика фиксированных точек, реляционные машины и вычислительная сложность» . Журнал АКМ . 44 (1): 30–56. дои : 10.1145/256292.256295 . ISSN 0004-5411 . S2CID 11338470 .

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

[8] Роберт., Макнотон (1971). Автоматы без счетчиков . МТИ Пресс. ISBN 0-262-13076-9 . OCLC 651199926 .

[9] Иммерман 1999, с. 22

[10] Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» . SIAM Journal по вычислительной технике . 17 (5): 935–938. дои : 10.1137/0217058 . ISSN 0097-5397 .

[:2-11] Jump up to: ^а ^б Иммерман 1999, с. 153–4

[12] Иммерман, Нил (1986). «Реляционные запросы, вычисляемые за полиномиальное время» . Информация и контроль . 68 (1–3): 86–104. дои : 10.1016/s0019-9958(86)80029-8 .

[13] Варди, Моше Ю. (1982). «Сложность реляционных языков запросов (расширенное резюме)». Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 137–146. CiteSeerX 10.1.1.331.6045 . дои : 10.1145/800070.802186 . ISBN 978-0897910705 . S2CID 7869248 .

[avv-14] Серж Абитебул, Моше Ю. Варди , Виктор Виану : Логика фиксированных точек, реляционные машины и вычислительная сложность Журнал архива ACM, Том 44, Выпуск 1 (январь 1997 г.), Страницы: 30-56, ISSN 0004-5411

[15] Гредель, Эрих (13 июля 1992 г.). «Захват классов сложности фрагментами логики второго порядка» . Теоретическая информатика . 101 (1): 35–57. дои : 10.1016/0304-3975(92)90149-А . ISSN 0304-3975 .

[16] Иммерман 1999, с. 115

[17] Иммерман 1999, с. 121

[18] Иммерман 1999, с. 181

[19] Абитбул, С.; Виану, В. (1989). «Расширения Fixpoint логики первого порядка и языков, подобных журналам данных» . [1989] Труды. Четвертый ежегодный симпозиум по логике в информатике . IEEE-компьютер. Соц. Нажимать. стр. 71–79. дои : 10.1109/lics.1989.39160 . ISBN 0-8186-1954-6 . S2CID 206437693 .

[20] Харель, Д.; Пелег, Д. (1 января 1984 г.). «О статической логике, динамической логике и классах сложности» . Информация и контроль . 60 (1): 86–102. дои : 10.1016/S0019-9958(84)80023-6 . ISSN 0019-9958 .

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]