Masalah lengkap alami di tingkat yang lebih tinggi dari hirarki-

The -hierarchy adalah hirarki kelas kompleksitas W [ t ] dalam kompleksitas parameter, lihat Zoo Kompleksitas untuk definisi. Definisi alternatif mendefinisikan W [ t ] menggunakan pembobotan Fagin tertimbang untuk Π t- formula logika orde pertama, lihat buku teks oleh Flum dan Grohe .$\mathsf{W}$$\mathsf{W}[t]$$\mathsf{W}[t]$$\Pi_t$

Untuk kelas terendah dan W [ 2 ] , banyak masalah alami lengkap diketahui, misalnya Clique dan Independent Set lengkap untuk W [ 1 ] , dan Dominating Set dan Hitting Set lengkap untuk W [ 2 ] , di mana masing-masing masalah ini didefinisikan sebagai yang sesuai terkenal N P masalah -Lengkap dengan ukuran set solusi yang diperlukan sebagai parameter. $\mathsf{W}[1]$$\mathsf{W}[2]$$\mathsf{W}[1]$$\mathsf{W}[2]$$\mathsf{NP}$

Adakah masalah alami lengkap yang diketahui untuk kelas yang lebih tinggi di hirarki- , khususnya untuk W [ 3 ] dan W [ 4 ] ?$\mathsf{W}$$\mathsf{W}[3]$$\mathsf{W}[4]$

Dari komentar di atas:

-HYPERGRAPH- (NON) -DOMINATING-SET$p$adalah W [3] -lengkap di bawah fpt-reduksi:

Hypergraph terdiri dari satu set V dari simpul dan satu set E dari hyperedges. Setiap hyperedge adalah sebagai bagian dari V . Dalam 3-hypergraph semua sisi memiliki ukuran 3. Jika H = ( V , E ) adalah 3-hypergraph, setiap a ∈ V menginduksi grafik H a = ( V a , E a ) yang diberikan oleh:$H = (V,E)$$V$$E$$V$$H = (V,E)$$a \in V$$H^a = (V^a, E^a)$

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

Input : A 3-hypergraph , himpunan M ⊆ V , dan k ≥ 1 . Parameter : k . Masalah : Putuskan apakah ada set D ⊆ V kardinalitas k sedemikian rupa sehingga:$H = (V,E)$$M \subseteq V$$k \geq 1$
$k$
$D \subseteq V$$k$

• jika , maka D adalah satu set mendominasi H a ,$a \in M$$D$$H^a$
• jika , maka D bukanlah himpunan dominan dari H a .$a \notin M$$D$$H^a$

lihat Yijia Chen, Jörg Flum dan Martin Grohe. Analisis Hirarki W *. Jurnal Logika Simbolik, Vol. 72, No. 2 (Jun., 2007), hlm. 513-534

Saya percaya judul makalah ini cukup jelas dan menjawab pertanyaan Anda: Mengenai produk yang mencakup model rantai pasokan 3-tier: Masalah lengkap alami untuk W [3] dan W [4]