П и Описательная Сложность

В зоопарке сложности говорится [ 1 ], что в описательной сложности может быть определен тремя различными типами формул: который также является , а также как .$P$$FO(LFP)$$FO(n^{O(1)})$$SO(HORN)$

Однако есть некоторые исключения, например, не может быть выражена FP (FP обладает такой же выразительной силой, что и LFP). и не определяются логикой первого порядка. Некоторые проблемы даже не могут быть аксиоматизированы с помощью конечного числа переменных, таких как , , .$Evenness$$Connectivity$$2-colourability$$Evenness$$Perfect~Matching$$Hamiltonicity$

Иммерман предположил, что логика фиксированных точек + подсчет (FPC) могут быть возможной логикой для захвата P.

Тем не менее, Cai Furer, Immerman показал, что существуют свойства графа полиномиального времени, которые не выражаются в FPC [ 2 ]. Задача решения линейных уравнений над двухэлементным полем не определима в бесконечной логике со счетом [ 3 ]. Вы можете обратиться к [ 4 ] для более подробной информации.

Итак, какая логическая структура может захватить P в целом? Положительный ответ заключается в том, что класс упорядоченных конечных структур определим в логике наименьшей неподвижной точки тогда и только тогда, когда он разрешим в P по Иммерману [ 5 ] и Варди [ 6 ]. Как насчет неупорядоченного дела? Можете ли вы показать больше контрпримеров утверждения в зоопарке сложности?

В последнее время Мартин Грохе добился существенного прогресса в этом вопросе. Он дает логику захвата полиномиального времени на классах графов, встраиваемых в фиксированную поверхность: https://dl.acm.org/citation.cfm?doid=2371656.2371662 Редактировать: общий случай кажется нерешенным (но я ни в коем случае не решаюсь) эксперт по этому вопросу).