Соответствие между классами сложности и логикой

Я взял класс один раз по вычислимости и логики. Материал содержал корреляцию между классами сложности / вычислимости (R, RE, co-RE, P, NP, Logspace, ...) и логикой (исчисление предикатов, логика первого порядка, ...).

Корреляция включала в себя несколько результатов в одной области, которые были получены с использованием методов из другой области. Предполагалось, что P! = NP может быть атакован как проблема в логике (путем проецирования проблемы из области классов сложности в логику).

Есть хорошее резюме этих методов и результатов?

Возможно, вы спрашиваете о результатах в теории конечных моделей (таких как характеристика P и NP с точки зрения различных фрагментов логики). Недавняя попытка доказательства P! = NP изначально широко использовала такие концепции, и некоторые хорошие ссылки (взяты из вики )

• Эрих Градель в обзоре FMT и описательной сложности
• Статья Рона Фагина о описательной сложности

Нил Иммерман создал красивую диаграмму, которая обеспечивает краткие соответствия между классами сложности и логикой, интерпретируемой конечными моделями. Это на обложке его книги, а также в нижней части его веб-страницы здесь: http://www.cs.umass.edu/~immerman/

$NP$

$S^1_2$

Антонина Колоколова работала над отношениями между этими двумя подходами.

Для тех, кто не знаком с множеством аббревиатур, найденных в великолепной диаграмме Иммермана, есть статья в Википедии о сложности описания . Должна быть диаграмма со ссылками, чтобы вы могли непосредственно искать определение в Сложности Зоопарка и других источниках. Я также хотел бы лучше увидеть отношения с соответствующими формальными языками / грамматиками и где вы можете найти доказательство.

Это не ответ, а комментарий к ответу Аарона, который я почему-то не могу прокомментировать.