HO (сложность) - Википедия - HO (complexity)

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

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

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

HO это набор формул, в которых порядок переменных не более . HO - подмножество формул вида куда квантификатор, Значит это набор переменных порядка с такой же количественной оценкой. Итак, это набор формул с чередования кванторов й порядок, начиная с и , а затем формула порядка .

С использованием тетрация стандартные обозначения, и . с раз

Свойство

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

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

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

HO равно НАЧАЛЬНЫЙ функции. Если быть более точным, , это означает башню 2s, заканчивающиеся на куда является константой. Частным случаем этого является то, что , что и есть Теорема Феджина. С помощью машины-оракулы в полиномиальная иерархия,

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

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

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