Zgodność między klasami złożoności a logiką

Raz wziąłem klasę na temat obliczalności i logiki. Materiał zawiera korelację między klasami złożoności / obliczalności (R, RE, co-RE, P, NP, Logspace, ...) i Logiką (rachunek predykatów, logika pierwszego rzędu, ...).

Korelacja obejmowała kilka wyników w jednym polu, które zostały uzyskane przy użyciu technik z drugiego pola. Przypuszczano, że P! = NP może zostać zaatakowany jako problem w Logice (poprzez rzutowanie problemu z dziedziny klas złożoności na logikę).

Czy istnieje dobre podsumowanie tych technik i wyników?

Możliwe, że pytasz o wyniki w teorii modeli skończonych (takie jak charakterystyka P i NP pod względem różnych fragmentów logiki). Niedawno podjęto próbę udowodnienia, że ​​P! = NP początkowo intensywnie wykorzystuje takie koncepcje, a niektóre dobre referencje (zaczerpnięte z wiki ) to

• Recenzja FMT i złożoności opisowej Ericha Gradela
• Artykuł Rona Fagina o złożoności opisowej

Neil Immerman stworzył piękny schemat, który zapewnia natychmiastowe powiązania między klasami złożoności a logiką interpretowaną przez modele skończone. Jest na okładce jego książki, a także na dole jego strony tutaj: http://www.cs.umass.edu/~immerman/

$NP$

$S^1_2$

Antonina Kolokolova pracowała nad relacjami między tymi dwoma podejściami.

Dla tych, którzy nie są zaznajomieni z mnóstwem akronimów znalezionych na wielkim diagramie Immermana, znajduje się artykuł w Wikipedii na temat złożoności opisowej . Powinien istnieć schemat z linkami, abyś mógł bezpośrednio wyszukać definicję w Zoo złożoności i innych źródłach. Chciałbym również lepiej zapoznać się z relacjami z odpowiednimi językami / gramatykami formalnymi i gdzie można znaleźć dowód.

To nie jest odpowiedź, ale komentarz do odpowiedzi Aaronsa, z której nie mogę komentować z jakiegoś powodu.