SNP (złożoność)

W teorii złożoności obliczeniowej SNP (od Strict NP ) jest klasą złożoności zawierającą ograniczony podzbiór NP w oparciu o jego logiczną charakterystykę pod względem teoretycznych właściwości grafów . Stanowi podstawę do zdefiniowania klasy MaxSNP problemów optymalizacyjnych .

Definiuje się go jako klasę problemów będących właściwościami struktur relacyjnych (takich jak grafy ) dającymi się wyrazić wzorem logicznym drugiego rzędu w postaci:

{\ Displaystyle \ istnieje S_ {1} \ dots \exists S_{\ell }\,\forall v_{1}\dots \forall v_{m}\,\phi (R_{1},\dots ,R_{k},S_{1},\dots , S_{\ell},v_{1},\kropki,v_{m})}

,

gdzie ${\ displaystyle R_ {1}, \ kropki, R_ {k}}$ są relacjami struktury (takimi jak relacja sąsiedztwa w przypadku wykresu), ${\ displaystyle S_ {1}, \ kropki, S _ {\ ell}}$ to nieznane relacje (zbiory krotek wierzchołków) i ${\ displaystyle \ phi}$ jest formułą bez kwantyfikatorów: dowolną kombinacją boolowską relacji. Oznacza to, że dozwolona jest tylko egzystencjalna kwantyfikacja drugiego rzędu (po relacjach) i dozwolona jest tylko uniwersalna kwantyfikacja pierwszego rzędu (po wierzchołkach). Gdyby dopuszczono również kwantyfikację egzystencjalną po wierzchołkach, otrzymana klasa złożoności byłaby równa NP (dokładniej klasie tych właściwości struktur relacyjnych, które są w NP), co jest faktem znanym jako twierdzenie Fagina .

Przykładowo SNP zawiera 3-Kolorowanie (problem określenia, czy dany graf jest 3-kolorowalny ), gdyż można to wyrazić wzorem:

{\ Displaystyle \ istnieje S_ {1} \ istnieje S_ {2} \ istnieje S_ {3} \, \ forall u \ forall v \, {\ bigl (} S_ {1} (u) \ vee S_ {2} ( u)\vee S_{3}(u){\bigr )}\,\wedge \,{\bigl (}E(u,v)\,\implies \,(\neg S_{1}(u)\ vee \neg S_{1}(v))\,\wedge \,\left(\neg S_{2}(u)\vee \neg S_{2}(v)\right)\,\wedge \,( \neg S_{3}(u)\vee \neg S_{3}(v)){\bigr )}}

.

Tutaj $)$ wykresu wejściowego, $odpowiadają$ jednoargumentowe do zbiorów wierzchołków pokolorowanych jednym z 3 kolorów. Podobnie SNP zawiera k -SAT: problem spełnialności logicznej (SAT), w którym formuła jest ograniczona do koniunkcyjnej postaci normalnej i co najwyżej k literałów na zdanie, gdzie k jest naprawiony.

MaxSNP

Analogiczna definicja dotyczy problemów optymalizacyjnych , gdy zamiast wymagać spełnienia formuły dla wszystkich krotek, chcemy maksymalizować liczbę krotek, dla których jest ona spełniona. Oznacza to, że MaxSNP ₀ definiuje się jako klasę problemów optymalizacyjnych na strukturach relacyjnych, które można wyrazić w następującej postaci:

{\ Displaystyle \ max \ limity _ {S_ {1}, \ kropki, S _ {\ ell}} | \ {(v_ {1}, \ kropki, v_ {m}) \ dwukropek \ phi (R_ {1}, \dots ,R_{k},S_{1},\dots ,S_{\ell},v_{1},\dots ,v_{m})\}|}

MaxSNP jest następnie definiowany jako klasa wszystkich problemów z redukcją L ( redukcja liniowa , a nie redukcja logarytmiczna ) do problemów w MaxSNP ₀ . Na przykład MAX-3SAT jest problemem w MaxSNP ₀ : biorąc pod uwagę instancję 3-CNF-SAT ( problem spełnialności logicznej formuły w koniunkcyjnej postaci normalnej i co najwyżej 3 literały na klauzulę), znajdź przypisanie spełniające tyle klauzul, ile możliwy. W rzeczywistości jest to naturalny, kompletny problem dla MaxSNP .

Istnieje algorytm aproksymacji o stałym współczynniku do rozwiązywania dowolnego problemu w MaxSNP , stąd MaxSNP jest zawarty w APX , klasie wszystkich problemów przybliżalnych w pewnym stałym stosunku. W rzeczywistości zamknięcie MaxSNP w ramach redukcji PTAS (nieco bardziej ogólne niż redukcje L) jest równe APX ; oznacza to, że każdy problem w APX ma redukcję PTAS z powodu jakiegoś problemu w MaxSNP . W szczególności każdy MaxSNP -complete (pod redukcjami L lub poniżej AP-redukcje ) jest również APX -kompletny (w ramach redukcji PTAS), a zatem nie dopuszcza PTAS, chyba że P=NP . Jednakże dowód tego opiera się na twierdzeniu PCP , podczas gdy dowody zupełności MaxSNP są często elementarne.

Zobacz też

APX

Gradel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maarten, Marks; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoria modelu skończonego i jej zastosowania . Teksty z informatyki teoretycznej. Seria EATCS. Berlin: Springer-Verlag . P. 350 . ISBN 978-3-540-00428-8 . Zbl 1133.03001 .

Linki zewnętrzne