P i złożoność opisowa

10

W zoo o złożoności napisano [ 1 ], że w złożoności opisowej można zdefiniować za pomocą trzech różnych rodzajów wzorów, który jest również , a także jako .PFO(LFP)FO(nO(1))SO(HORN)

Istnieją jednak pewne wyjątki, na przykład nie może być wyrażona przez FP (FP ma taką samą moc ekspresji z LFP). i nie można zdefiniować za pomocą logiki pierwszego rzędu. Niektórych problemów nie można nawet aksjatyzować za pomocą skończonej liczby zmiennych, takich jak , , .EvennessConnectivity2−colourabilityEvennessPerfect MatchingHamiltonicity

Immerman zaproponował, że logika stała + zliczanie (FPC) może być logiką możliwą do przechwycenia P.

Jednak Cai Furer, Immerman wykazał, że istnieją właściwości wykresu wielomianowego, które nie są wyrażalne w FPC [ 2 ]. Problem rozwiązywania równań liniowych nad polem dwuelementowym nie jest definiowany w logice nieskończonej z liczeniem [ 3 ]. Więcej informacji można znaleźć w [ 4 ].

Więc jaka struktura logiczna może przechwycić P w ogóle? Pozytywną odpowiedzią jest to, że klasa uporządkowanych struktur skończonych jest definiowalna w logice co najmniej stałoprzecinkowej wtedy i tylko wtedy, gdy jest rozstrzygalna w P przez Immermana [ 5 ] i Vardiego [ 6 ]. Co powiesz na nieuporządkowaną sprawę? Czy możesz pokazać więcej kontrprzykładów oświadczenia w złożonym zoo?

lo.logic polynomial-time descriptive-complexity Rupei Xu
źródło
2
Oto samouczek zawierający przegląd wyników tego konkretnego pytania: cl.cam.ac.uk/~ad260/talks/wollic-tutorial.pdf
Denis
@Denis Dziękuję, Denis! Ten samouczek zawiera więcej struktur logicznych dla P. Tradycyjnie, kiedy mówimy o problemie, można rozwiązać czas wielomianowy, uważamy, że jest to „łatwe”. Jednak struktury logiczne P wyglądają na tak skomplikowane i wciąż istnieje wiele nieznanych przypadków i otwartych problemów.
Rupei Xu,
1
Tak, wydaje się, że zestaw „łatwych” problemów (tj. P) nie jest tak dobrze ustrukturyzowany i trudno jest go scharakteryzować za pomocą czegoś takiego jak „łatwe problemy to takie, które można uzyskać z podstawowych problemów A, B, C, połączone na różne sposoby X, Y ”. Zawsze są łatwiejsze problemy, które są innego rodzaju i wymagają sprytnych algorytmów wielomianowych z nowymi pomysłami.
Denis

Odpowiedzi:

2

Martin Grohe poczynił ostatnio znaczne postępy w tej kwestii. Podaje logikę przechwytującą wielomian czasu na klasach grafów, które można osadzić na stałej powierzchni: https://dl.acm.org/citation.cfm?doid=2371656.2371662 Edycja: ogólny przypadek wydaje się nierozwiązany (ale ja w żadnym wypadku ekspert w tej dziedzinie).

Hermann Gruber
źródło
Tak. Istnieje wiele algorytmicznych wyników meta-twierdzeń (takich jak słynne twierdzenie Courcelle'a), które mogą uchwycić łatwe przypadki, poniższy link to dobry artykuł ankietowy. people.cs.umass.edu/~immerman/pub/… Jednak wyniki te mają również ograniczenia dotyczące struktur grafowych, na których działa problem, takich jak drzewo, ograniczona szerokość, wykresy płaskie, małe zamknięte wykresy itp. Istnieją żadna kompletna struktura logiczna nie jest w stanie uchwycić P na ogólnych wykresach bez kolejności.
Rupei Xu,
Wydaje mi się, że praca Grohe jest dość wyjątkowa, ponieważ w takim przypadku logika wyczerpuje całe P na niezwykle dużej klasie grafów, tzn. Nie ma kontrprób. Jeśli mam rację, bycie wyczerpującym jest trudną częścią. Wyniki MSO, o których wspomniałeś, nie mają tej funkcji. Ale moja wiedza w tym zakresie jest bardzo ograniczona, mogę się tutaj mylić.
Hermann Gruber