FPT vs W [P] - Complexidade parametrizada

20

Na complexidade parametrizada, . É conjecturado que cada uma das contenções é adequada.W [ 2 ] W [ P ]FPTW[1] W[2] W[P]

Se então .P = W [ P ]FPT=W[P]P=W[P]

Mas segue que

  • Se então ? ouF P T = W [ P ]FPT=W[1]FPT=W[P]
  • Se (para alguns t), então ?F P T = W [ P ]W[t1]=W[t]FPT=W[P]
Uéverton dos santos souza
fonte
1
O que significa a notação "W []"?
Tyson Williams
1
A segunda pergunta significa "para todos os t" ou "para alguns t"?
Yoshio Okamoto
A segunda pergunta significa "para alguns t"
Uéverton dos santos souza
2
Você não está sendo um questionador útil. Você não incluiu definição ou links para a hierarquia W, mesmo que alguém tenha perguntado sobre isso. A resposta para suas perguntas é provavelmente "ambas estão abertas", devido à caracterização da hierarquia W como famílias de circuitos AC0 modificados - um colapso da hierarquia W implicaria um colapso da complexidade do circuito. (Isso é considerado uma evidência de que todos os níveis da hierarquia W são um subconjunto adequado do próximo.) Mas eu precisaria verificar algumas coisas para postar uma resposta (não minha área) e você não está levando a questão a sério.
Aaron Sterling
2
Um problema parametrizado (L, K) pertence a W [t] se existe k 'calculado a partir de k, de modo que (L, K) reduz o problema de satisfação do peso-k' para circuitos de trama-t. [Downey, 1997] [Downey, 1997] Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan; Série de Relatórios de Pesquisa Complexidade de Circuitos Parametrizados e Hierarquia W; Centro de Matemática Discreta e Ciência da Computação Teórica; 1997.
Uéverton dos santos souza

Respostas:

14

Essa pergunta é complicada, pois a resposta (até onde eu sei) ainda é "não sei".

Para acrescentar algum peso a isso, Flum & Grohe [1] apresentam como problemas em aberto (p. 164):

  • A hierarquia é estrita sob a suposição ?F P TW [ P ]WFPTW[P]
  • Para , a igualdade implica ?W [ t ] = W [ t + 1 ] W [ t ] = W [ t + 2 ]t1W[t]=W[t+1]W[t]=W[t+2]

Além disso, na recente monografia de Downey e Fellow [2], a declaração mais forte (direta) que eles fazem é (p. 521):

Uma hipótese mais sutil é que a hierarquia é adequada e, em particular, .W [ 1 ] W [ 2 ]WW[1]W[2]

Não há nenhuma declaração a seguir (ou posterior) ao longo das linhas "caso contrário, a hierarquia entraria em colapso" ou similar.W

Isso também é precedido por:

Uma hipótese mais fraca pode ser que, para alguns , F P TW [ t ]t

FPTW[t]

Isso implica que é possível que não tenha outros efeitos na hierarquia.FPT=W[t1]

Referências:

  1. J. Flum e M. Grohe, "Parameterized Complexity Theory", Springer, 2006.
  2. R. Downey e M. Fellows, "Fundamentos da teoria da complexidade parametrizada", Springer, 2014.
Luke Mathieson
fonte