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

33

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?

ripper234
źródło

Odpowiedzi:

23

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

Suresh Venkat
źródło
Myślę, że zakres FMT jest nieco szerszy niż tylko połączenie logiki i złożoności obliczeniowej. Złożoność opisowa wydaje się bardziej precyzyjnym terminem.
András Salamon,
24

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/

Aaron Sterling
źródło
To zdjęcie jest warte wielu tysięcy słów.
András Salamon,
5
Książka Immermana jest prawdopodobnie najlepszym pojedynczym odniesieniem do bezpośrednich powiązań między logiką a złożonością obliczeniową. Temat ten nazywa się zwykle „złożonością opisową”, podobnie jak książka.
András Salamon,
16

NP

S21

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

Kaveh
źródło
11

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.

Jakob
źródło
potrzebujesz trochę więcej przedstawicieli, aby opublikować komentarz (jest to mechanizm blokujący spam).
Suresh Venkat