FPT vs W [P] - sparametryzowana złożoność

W sparametryzowanej złożoności . Przypuszcza się, że każda zawartość jest właściwa. $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$

Jeśli to . $\mathsf{FPT}=\mathsf{W}[P]$ $\mathsf{P}=\mathsf{W}[P]$

Ale czy to wynika z tego

Jeśli to ? lub $\mathsf{FPT}=\mathsf{W}[1]$ $\mathsf{FPT}=\mathsf{W}[P]$
Jeśli (dla niektórych t) to ? $\mathsf{W}[t-1]=\mathsf{W}[t]$ $\mathsf{FPT}=\mathsf{W}[P]$

cc.complexity-theory parameterized-complexity fixed-parameter-tractable

— Uéverton dos Santos Souza
źródło

Co oznacza notacja „W []”?

— Tyson Williams,

Czy drugie pytanie oznacza „dla wszystkich t” czy „dla niektórych t”?

— Yoshio Okamoto

Drugie pytanie oznacza „dla niektórych t”

— Uéverton dos Santos Souza

Nie jesteś pomocnym pytającym. Nie podałeś definicji ani linków do hierarchii W, nawet jeśli ktoś Cię o to zapytał. Odpowiedź na twoje pytania jest prawdopodobnie „obie są otwarte” ze względu na charakterystykę hierarchii W jako rodzin zmodyfikowanych obwodów AC0 - załamanie hierarchii W oznaczałoby załamanie złożoności obwodów. (Jest to uważane za dowód, że każdy poziom hierarchii W jest właściwym podzbiorem następnego.) Ale musiałbym sprawdzić kilka rzeczy, aby opublikować odpowiedź (nie moją dziedzinę), a ty nie traktujesz tego poważnie.

— Aaron Sterling

Problem sparametryzowany (L, K) należy do W [t], jeżeli istnieje k 'obliczone z k takie, że (L, K) redukuje się do problemu zadowolenia masy-k' dla obwodów wątkowych-t. [Downey, 1997] [Downey, 1997] Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan; Raport z badań Seria sparametryzowana złożoność obwodu i hierarchia W. Centrum Matematyki Dyskretnej i Informatyki Teoretycznej; 1997.

— Uéverton dos santos souza

To pytanie jest trudne, ponieważ odpowiedź (o ile wiem) wciąż brzmi „nie wiem”.

Aby dodać do tego trochę wagi, Flum i Grohe [1] podają jako otwarte problemy (s. 164):

Czy hierarchia jest ścisła przy założeniu ? $\mathrm{W}$ $\mathrm{FPT} \neq \mathrm{W[P]}$

Czy dla równość oznacza ? $t \geq 1$ $\mathrm{W}[t] = \mathrm{W}[t + 1]$ $\mathrm{W}[t] = \mathrm{W}[t + 2]$

Co więcej, w najnowszej monografii Downey i Fellow [2] najsilniejszym (wprost) stwierdzeniem, jakie piszą jest (s. 521):

Bardziej subtelna hipoteza jest taka, że hierarchia jest poprawna, aw szczególności . $\mathrm{W}$ $\mathrm{W}[1] \neq \mathrm{W}[2]$

Nie ma następującej (lub późniejszej) instrukcji w stylu „inaczej hierarchia zawaliłaby się” lub podobnie. $\mathrm{W}$

Poprzedza to również:

Słabszą hipotezą może być to, że dla niektórych , $t$
$F P T \neq W [t]$ $\mathrm{FPT} \neq \mathrm{W}[t]$

Sugeruje to, że bez innych skutków dla hierarchii. $\mathrm{FPT} = \mathrm{W}[t-1]$

Bibliografia:

J. Flum i M. Grohe, „Parameterized Complexity Theory”, Springer, 2006.
R. Downey i M. Fellows, „Podstawy sparametryzowanej teorii złożoności”, Springer, 2014.

— Luke Mathieson
źródło