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