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