HO (сложность) - HO (complexity) - Wikipedia

Логика высокого порядка является расширением первый заказ и второго порядка с кванторами высокого порядка. В описательная сложность мы видим, что он равен НАЧАЛЬНЫЙ функции.^[1] Есть связь между ${\displaystyle i}$-го порядка и недетерминированный алгоритм, время которого с ${\displaystyle i-1}$ уровень экспонент.

Определения и обозначения

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

HO${\displaystyle ^{i}}$ это набор формул, в которых порядок переменных не более ${\displaystyle i}$. HO${\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}$ чередования кванторов ${\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}$

Свойство

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

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

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

HO равно НАЧАЛЬНЫЙ функции. Если быть более точным, ${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$, это означает башню ${\displaystyle (i-2)}$ 2s, заканчивающиеся на ${\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. Лаури Хелла и Хосе Мария Турулл-Торрес (2006), «Вычисление запросов с логикой высшего порядка», Теоретическая информатика ((что в bibtex называется «числом») изд.), Эссекс, Великобритания: Elsevier Science Publishers Ltd., 355 (2): 197–214, Дои:10.1016 / j.tcs.2006.01.009, ISSN  0304-3975

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

• зоопарк о HO.