FO (сложность) - FO (complexity)

В описательная сложность, филиал вычислительная сложность, FO это класс сложности структур, которые можно распознать по формулам логика первого порядка, а также равен классу сложности AC⁰. В описательной сложности используется формализм логики, но не используются несколько ключевых понятий, связанных с логикой, таких как теория доказательств или аксиоматизация.

Ограничение предикатов быть из набора Икс дает FO меньшего класса [Икс]. Например, FO [<] - это набор языки без звезд. Два разных определения FO [<], с точки зрения логики и с точки зрения регулярных выражений, предполагают, что этот класс может быть математически интересен помимо его роли в вычислительной сложности, и что методы как из логических, так и из регулярных выражений могут быть полезны в его изучать.

Точно так же расширения логики первого порядка, образованные добавлением операторов, порождают другие хорошо известные классы сложности.^[1] Это позволяет установить сложность некоторых проблем без ссылки на алгоритмы.

Определение и примеры

Идея

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

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

Формально

Позволять Икс быть набором предикатов на ${displaystyle mathbb {N} }$. Язык FO [Икс] определяется как замыкание конъюнкцией (${displaystyle wedge }$), отрицание (${displaystyle eg }$) и универсальная количественная оценка (${displaystyle forall }$) над элементами конструкций. Экзистенциальная количественная оценка (${displaystyle exists }$) и дизъюнкция (${displaystyle vee }$) также часто используются, но их можно определить с помощью первых трех символов. Базовый случай - это предикаты Икс применяется к некоторым переменным. Всегда неявно есть предикат ${displaystyle P_{a}(x)}$ за каждую букву а алфавита, заявив, что буква в позиции Икс является а.

Семантика формул в FO проста, ${displaystyle eg A}$ верно, если и только если А ложно, ${displaystyle Awedge B}$ верно, если и только если А правда и B правда, и ${displaystyle forall xP(x)}$ верно, если и только если ${displaystyle P(v)}$ верно для всех значений v который Икс может проникнуть в нижележащую вселенную. За п а c-арный предикат, ${displaystyle P(x_{1},dots ,x_{c})}$ верно тогда и только тогда, когда ${displaystyle x_{i}}$ интерпретируется как ${displaystyle n_{i}}$ ${displaystyle P(n_{1},dots ,n_{c})}$ правда.

Свойство

Предупреждение

Запрос в FO будет тогда проверять, верна ли формула первого порядка для данной структуры, представляющей входные данные для проблемы. Не следует путать этот вид проблемы с проверкой истинности количественной логической формулы, которая является определением QBF, который PSPACE-полный. Разница между этими двумя проблемами заключается в том, что в QBF размер проблемы - это размер формулы, а элементы - это просто логические переменные, тогда как в FO размер проблемы - это размер структуры, а формула фиксирована.

Это похоже на Параметризованная сложность но размер формулы не является фиксированным параметром.

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

Без учета пустых структур каждая формула эквивалентна формуле в пренекс нормальная форма (где сначала записываются все кванторы, а затем формула без кванторов).

Операторы

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

В сложность схемы, FO (ARB), где ARB - это набор всех предикатов; можно показать, что логика, в которой мы можем использовать произвольные предикаты, равна AC⁰, первый класс в AC иерархия. В самом деле, существует естественный перевод символов FO в узлы цепей, где ${displaystyle forall ,exists }$ существование ${displaystyle land }$ и ${displaystyle lor }$ размера п.

FO (BIT) - ограничение AC⁰ семейство схем, построенных в переменное логарифмическое время. FO (<) - множество языки без звезд.

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

FO (PFP,Икс) - это набор логических запросов, определяемых в FO (X), куда мы добавляем частичный оператор с фиксированной точкой.

Позволять k быть целым числом, ${displaystyle x,y}$ быть векторами k переменные, п быть переменной второго порядка арности k, и φ быть функцией FO (PFP, X), используя Икс и п как переменные. Мы можем итеративно определить ${displaystyle (P_{i})_{iin N}}$ такой, что ${displaystyle P_{0}(x)=false}$ и ${displaystyle P_{i}(x)=phi (P_{i-1},x)}$ (смысл φ с ${displaystyle P_{i-1}}$ заменена на переменную второго порядка п). Тогда либо есть фиксированная точка, либо список ${displaystyle (P_{i})}$s циклический.

${displaystyle operatorname {PFP} (phi _{P,x})(y)}$ определяется как значение фиксированной точки ${displaystyle (P_{i})}$ на у если есть фиксированная точка, иначе как ложь. С пs - свойства арности k, есть не более ${displaystyle 2^{n^{k}}}$ ценности для ${displaystyle P_{i}}$s, поэтому с помощью счетчика полиномиального пространства мы можем проверить, есть ли цикл или нет.

Доказано, что FO (PFP, BIT) равно PSPACE. Это определение эквивалентно ${displaystyle {mathsf {FO}}[2^{n^{O(1)}}]}$.

Наименьшая фиксированная точка - P

FO (LFP, X) - это набор логических запросов, определяемых в FO (PFP, X), где частичная фиксированная точка ограничена монотонностью. То есть, если переменная второго порядка п, тогда ${displaystyle P_{i}(x)}$ всегда подразумевает ${displaystyle P_{i+1}(x)}$.

Мы можем гарантировать монотонность, ограничив формулу φ содержать только положительные вхождения п (то есть события, которым предшествует четное число отрицаний). В качестве альтернативы мы можем описать ${displaystyle operatorname {LFP} (phi _{P,x})}$ в качестве ${displaystyle operatorname {PFP} (psi _{P,x})}$ куда ${displaystyle psi (P,x)=phi (P,x)vee P(x)}$.

Из-за монотонности мы добавляем только векторы в таблицу истинности п, а поскольку есть только ${displaystyle n^{k}}$ возможных векторов мы всегда найдем фиксированную точку перед ${displaystyle n^{k}}$ итераций. Теорема Иммермана-Варди, независимо доказанная Иммерман^[2] и Варди,^[3] показывает, что FO (LFP, BIT) =п. Это определение эквивалентно ${displaystyle {mathsf {FO}}[n^{O(1)}]}$.

Транзитивное закрытие - NL

FO (TC, X) - это набор логических запросов, определяемых в FO (X) с помощью переходное закрытие (TC) оператор.

TC определяется так: пусть k быть положительным целым числом и ${displaystyle u,v,x,y}$ быть вектором k переменные. потом ${displaystyle {mathsf {TC}}(phi _{u,v})(x,y)}$ верно, если существует п векторы переменных ${displaystyle (z_{i})}$ такой, что ${displaystyle z_{1}=x,z_{n}=y}$, и для всех ${displaystyle i<n}$, ${displaystyle phi (z_{i},z_{i+1})}$ правда. Здесь, φ - формула, записанная в FO (TC) и ${displaystyle phi (x,y)}$ означает, что переменные ты и v заменены на Икс и у.

FO (TC, BIT) равно NL.

Детерминированное транзитивное замыкание - это L

FO (DTC, X) определяется как FO (TC, X), где оператор транзитивного замыкания является детерминированным. Это означает, что когда мы применяем ${displaystyle operatorname {DTC} (phi _{u,v})}$, мы знаем, что для всех ты, существует не более одного v такой, что ${displaystyle phi (u,v)}$.

Можно предположить, что ${displaystyle operatorname {DTC} (phi _{u,v})}$ является синтаксический сахар за ${displaystyle operatorname {TC} (psi _{u,v})}$ куда ${displaystyle psi (u,v)=phi (u,v)wedge forall x(x=vvee eg phi (u,x))}$.

Было показано, что FO (DTC, BIT) равно L.

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

Любую формулу с оператором фиксированной точки (соответственно, транзитивным замыканием) можно без ограничения общности записать с ровно одним применением операторов к 0 (соответственно. ${displaystyle 0,(n-1)}$)

Итерация

Мы определим первый порядок с итерацией, ${displaystyle {mathsf {FO}}[t(n)]}$; здесь ${displaystyle t(n)}$ представляет собой (класс) функций от целых чисел до целых, и для различных классов функций ${displaystyle t(n)}$ получим разные классы сложности ${displaystyle {mathsf {FO}}[t(n)]}$.

В этом разделе мы напишем ${displaystyle (forall xP)Q}$ значить ${displaystyle (forall x(PRightarrow Q))}$ и ${displaystyle (exists xP)Q}$ значить ${displaystyle (exists x(Pwedge Q))}$. Сначала нам нужно определить блоки кванторов (QB), блок кванторов - это список ${displaystyle (Q_{1}x_{1},phi _{1})...(Q_{k}x_{k},phi _{k})}$ где ${displaystyle phi _{i}}$s не содержат кванторов FO -формулы и ${displaystyle Q_{i}}$s либо ${displaystyle forall }$ или же ${displaystyle exists }$.Если Q блок квантификаторов, тогда мы будем называть ${displaystyle [Q]^{t(n)}}$ оператор итерации, который определяется как Q написано ${displaystyle t(n)}$ время. Следует обратить внимание, что здесь есть ${displaystyle k*t(n)}$ кванторы в списке, но только k переменные, и каждая из этих переменных используется ${displaystyle t(n)}$ раз.

Теперь мы можем определить ${displaystyle {mathsf {FO}}[t(n)]}$ быть FO-формулами с итерационным оператором, экспонента которого находится в классе ${displaystyle t(n)}$, и получаем эти равенства:

• ${displaystyle {mathsf {FO}}[(log n)^{i}]}$ равно FO-uniform AC^я, а на самом деле ${displaystyle {mathsf {FO}}[t(n)]}$ FO-однородный АС глубины ${displaystyle t(n)}$.
• ${displaystyle {mathsf {FO}}[(log n)^{O(1)}]}$ равно NC.
• ${displaystyle {mathsf {FO}}[n^{O(1)}]}$ равно PTIME, это также еще один способ записи FO (LFP).
• ${displaystyle {mathsf {FO}}[2^{n^{O(1)}}]}$ равно PSPACE, это еще один способ написать FO (PFP).

Логика без арифметических соотношений

Пусть отношение преемника, succ, - бинарное отношение такое, что ${displaystyle operatorname {succ} (x,y)}$ верно тогда и только тогда, когда ${displaystyle x+1=y}$.

По логике первого порядка, succ строго менее выразительно, чем <, который менее выразителен, чем +, который менее выразителен, чем кусочек, а + и × выразительны, как кусочек.

Использование преемника для определения кусочек

Можно определить плюс а затем кусочек отношения с детерминированным транзитивным замыканием.

${displaystyle operatorname {plus} (a,b,c)=(operatorname {DTC} _{v,x,y,z}operatorname {succ} (v,y)land operatorname {succ} (z,x))(a,b,c,0)}$ и

${displaystyle operatorname {bit} (a,b)=(operatorname {DTC} _{a,b,a',b'}psi )(a,b,1,0)}$ с

${displaystyle psi ={ ext{if }}b=0{ ext{ then }}({ ext{if }}exists m(a=m+m+1){ ext{ then }}(a'=1land b'=0){ ext{ else }}ot ){ ext{ else }}(operatorname {succ} (b',b)land (a+a=a'lor a+a+1=a')}$

Это просто означает, что когда мы запрашиваем бит 0, мы проверяем четность и переходим к (1,0), если а нечетное (принимающее состояние), иначе мы отклоняем. Если мы немного проверим ${displaystyle b>0}$, мы делим а на 2 и проверить бит ${displaystyle b-1}$.

Следовательно, нет смысла говорить об операторах с одним преемником без других предикатов.

Логика без преемника

FO [LFP] и FO [PFP] - это две логики без каких-либо предикатов, кроме предикатов равенства между переменными и предикатами букв. Они равны соответственно реляционный-P и FO (PFP) - это реляционный-PSPACE, классы P и PSPACE над реляционные машины.^[4]

В Теорема Абитебула-Виану утверждает, что FO (LFP) = FO (PFP) тогда и только тогда, когда FO (<, LFP) = FO (<, PFP), следовательно, тогда и только тогда, когда P = PSPACE. Этот результат был распространен на другие фиксированные точки.^[4] Это показывает, что проблема первого порядка является скорее технической проблемой, чем фундаментальной.

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

• Рональд Феджин, Обобщенные спектры первого порядка и распознаваемые множества за полиномиальное время. Сложность вычислений, изд. Р. Карп, SIAM-AMS Proceedings 7, pp. 27–41. 1974 г.
• Рональд Феджин, Теория конечных моделей - личная перспектива. Теоретическая информатика 116, 1993, стр. 3–31.
• Нил Иммерман. Языки, охватывающие классы сложности. 15-й симпозиум ACM STOCС. 347–354. 1983 г.

1. Иммерман, Нил (1999). Описательная сложность. Springer. ISBN  978-0-387-98600-5.
2. Иммерман, Нил (1986). «Реляционные запросы, вычислимые за полиномиальное время». Информация и контроль. 68 (1–3): 86–104. Дои:10.1016 / с0019-9958 (86) 80029-8.
3. Варди, Моше Й. (1982). Сложность языков реляционных запросов (Расширенная аннотация). Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений. STOC '82. Нью-Йорк, Нью-Йорк, США: ACM. С. 137–146. CiteSeerX  10.1.1.331.6045. Дои:10.1145/800070.802186. ISBN  978-0897910705.
4. Серж Абитебул, Моше Й. Варди, Виктор Виану: Логика Fixpoint, реляционные машины и вычислительная сложность Журнал архива ACM, том 44, выпуск 1 (январь 1997 г.), Страницы: 30-56, ISSN  0004-5411

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

• Страница описательной сложности Нила Иммермана, включая схему
• Сложность зоопарка о ФО см. также следующие классы