Naturalne kompletne problemy na wyższych poziomach hierarchii

13

-hierarchy hierarchia klas złożoność w sparametryzowanej złożoności patrz Zoo złożoność definicje. Alternatywna definicja definiuje przy użyciu ważonej definiowalności Fagina dla logiki pierwszego rzędu, patrz podręcznik Fluma i Grohe . $\mathsf{W}$ $\mathsf{W}[t]$ $\mathsf{W}[t]$ $\Pi_t$

Dla najniższych klas i , znanych jest wiele naturalnych kompletnych problemów, np. Clique i zestaw niezależny są kompletne dla oraz Dominating Set i Zestaw trafień jest kompletny dla , gdzie każdy z tych problemów jest zdefiniowany jako odpowiadający dobrze znany -kompletny problem z rozmiarem wymaganego zestawu rozwiązań jako parametru. $\mathsf{W}[1]$ $\mathsf{W}[2]$ $\mathsf{W}[1]$ $\mathsf{W}[2]$ $\mathsf{NP}$

Czy są jakieś znane naturalne kompletne problemy dla klas wyżej w hierarchii , w szczególności dla i ? $\mathsf{W}$ $\mathsf{W}[3]$ $\mathsf{W}[4]$

cc.complexity-theory parameterized-complexity Jan Johannsen
źródło

2

W tym artykule udowodniono, że p-HYPERGRAPH- (NON) -DOMINATING-SET jest W [3] -kompletny w ramach redukcji Fpt ... ale myślę, że trudno jest uznać to za „naturalne” :-) :-)

Marzio De Biasi,

2

Cóż, przynajmniej wygląda to bardziej naturalnie niż problemy definiujące, prawda?

Jan Johannsen,

11

Z powyższego komentarza:

$p$ HYPERGRAPH- (NIE) -DOMINUJĄCY-ZESTAW jest W [3] -kompletny w ramach redukcji fpt:

Hipergraph składa się z zestawu wierzchołków i zestawu hipergeuszy. Każdy hyperedge jest podgrupie . W hipergraphie 3 wszystkie krawędzie mają rozmiar 3. Jeśli jest hipergraphem 3, każde indukuje wykres podany przez: $H = (V,E)$ $V$ $E$ $V$ $H = (V,E)$ $a \in V$ $H^a = (V^a, E^a)$

$V^a = \{ v \in V \mid v \neq a \text{ and there is } e \in E \text{ with } a, v \in e \}$ i $E^a = \{ \{u,v\} \mid \{a,u,v\} \in E \}$

Dane wejściowe : A 3-hypergraph , zestaw i . Parametr : . Problem : Zdecyduj, czy istnieje zbiór liczności taki, że: $H = (V,E)$ $M \subseteq V$ $k \geq 1$
$k$
$D \subseteq V$ $k$

jeśli , to jest dominującym zbiorem , $a \in M$ $D$ $H^a$
jeśli , to nie jest dominującym zbiorem . $a \notin M$ $D$ $H^a$

patrz Yijia Chen, Jörg Flum i Martin Grohe. Analiza hierarchii W *. The Journal of Symbolic Logic, t. 72, nr 2 (czerwiec 2007 r.), Str. 513–534

Marzio De Biasi
źródło

13

Uważam, że tytuł tego artykułu nie wymaga wyjaśnień i odpowiada na twoje pytanie: dotyczące pokrycia produktu w 3-warstwowych modelach łańcucha dostaw: Naturalne kompletne problemy dla W [3] i W [4]

Yixin Cao
źródło

Definicje problemów w tym artykule nie są zbyt łatwe do odczytania, ponieważ autorzy nie dokonują wyraźnego rozróżnienia między modelem a tym, co jest modelowane. Ale o ile je rozumiem, są to tylko słabo ukryte problemy SAT z obwodem ważonym. Mogą być przydatne w domenie aplikacji, ale wątpię, czy można je bardziej zmniejszyć.

Jan Johannsen,

Częściowo zgadzam się z tobą, że problemy te nie są tak naturalne jak osłona wierzchołków / klika / dominujący zestaw itp. Ale przy coraz większej liczbie badanych problemów, ale bez pojawiania się nowych kandydatów, być może będziemy musieli zwrócić się do tych subnaturalnych problemów.

Yixin Cao,

Nie twierdzę, że te problemy nie są naturalne. Mówię tylko, że nie różnią się one bardzo od problemów ważonej SAT dla obwodów głębokości trzech. O ile rozumiem, są one mniej więcej tym samym problemem napisanym w innej terminologii.

Jan Johannsen

Naturalne kompletne problemy na wyższych poziomach hierarchii

Odpowiedzi: