Описательная теория сложности
-
Основы логики первого порядка
- Логика первого порядка (FO) — это формальная система, которая включает в себя переменные, кванторы и логические операции.
- Она используется для описания вычислительных задач и является основой для многих других логик.
-
Логика второго порядка
- Логика второго порядка (SO) расширяет FO, добавляя переменные более высокого порядка и кванторы второго порядка.
- Она позволяет описывать структуры, которые не могут быть описаны в FO.
-
Характеристики классов сложности
- Логика первого порядка используется для описания классов сложности P и NP.
- Логика второго порядка позволяет характеризовать классы сложности PSPACE и NP.
-
Теорема Иммермана-Варди
- Иммерман и Варди доказали, что FO [LFP] характеризует PTIME в упорядоченных структурах.
-
Формулы Хорна второго порядка
- SO-Horn — это класс формул, которые могут быть преобразованы в предварительные формулы в экзистенциальной логике Хорна второго порядка.
-
Недетерминированное полиномиальное время
- Теорема Феджина утверждает, что NP характеризуется классами структур, аксиоматизируемыми в экзистенциальной логике второго порядка.
-
Элементарные функции и классы сложности
- HO — это класс сложности, который включает в себя элементарные функции.
- HO
- j
- i
- это класс сложности, который описывает время работы недетерминированных алгоритмов, ограниченных
- уровнями экспонент.
-
Нормальная форма формул порядка
- Каждая формула порядка может быть представлена в нормальной форме, где количественная оценка переменных более высокого порядка следует за формулой порядка предыдущего порядка.
-
Отношение к классам сложности
- HO равно классу элементарных из элементарных функций и связано с классами сложности, такими как PSPACE и NP.
Полный текст статьи: