Instância de reduções de FPT que não são uma redução no tempo polinomial

11

Na complexidade parametrizada, as pessoas usam a redução de FPT (Trace-Parametrable-Fixed) para provar a dureza W [t]. Teoricamente, uma redução de FPT não é uma redução de tempo polinomial, pois pode ser executada exponencialmente no parâmetro k. Mas, na prática, todas as reduções de FPT que eu vi são reduções no tempo p, o que significa que as provas de dureza W [t] quase sempre implicam provas de completude de NP.

Gostaria de saber se alguém pode me dar uma redução de FPT que realmente é executada exponencialmente no parâmetro . Obrigado.k

yzll
fonte

Respostas:

11

Um exemplo inicial é a prova de dureza W [2] para o Conjunto Dominante de Torneio (Teorema 4.1 em [1]). A redução é de Dominating Set e constrói um torneio com vértices, em que n é o número de vértices da instância do conjunto dominante e k é o parâmetro.O(2kn)nk

[1]: Rodney G. Downey e Michael R. Fellows. Viabilidade computacional parametrizada. Em P. Clote e JB Remmel, editores, Proceedings of Feasible Mathematics II, páginas 219-244. Birkhauser, 1995.

Serge Gaspers
fonte
1
Uma prova (talvez diferente) da mesma afirmação também pode ser encontrada no livro "Parameterized Complexity Theory" de J. Flum e M. Grohe, Teorema 7.17.
Mathieu Chapelle
8

O documento a seguir contém reduções para várias parametrizações de Substring mais próximo, nas quais o tempo de execução depende exponencialmente ou do dobro exponencialmente do parâmetro (e essa dependência parece inevitável).

D. Marx. Problemas de substring mais próximos com pequenas distâncias . Revista Brasileira de Computação, 38 (4): 1382-1410, 2008.

Daniel Marx
fonte
6

Como complemento às outras respostas, a seguinte proposição mostra que as noções correspondentes de redutibilidade são incomparáveis:

(Q,k)(Q,k)(Q,k)<fpt(Q,k)Q<ptime Q

<fpt<ptime

[2]: J. Flum, M. Grohe. Teoria da complexidade parametrizada. Springer (2006)

Mathieu Chapelle
fonte
5

Provavelmente, essa não é uma resposta pretendida, mas que tal (uma variante aleatória) de código de cores para o problema do caminho k? http://en.wikipedia.org/wiki/Color-coding

Ali, transforma-se uma instância do problema do caminho k em instâncias do problema colorido do caminho k por uma redução de fpt com dependência super-polinomial de k. (Cria-se várias instâncias, mas elas podem ser vistas como uma grande instância.) Como o problema do caminho k colorido pode ser resolvido em tempo de fpt pela programação dinâmica, podemos concluir que o problema do caminho k pertence ao FPT.

Yoshio Okamoto
fonte
3

Outro exemplo dessa redução é a prova de dureza para a dimensão VC. Veja "Complexidade da aprendizagem parametrizada", de Downey, Evans e Fellows.

Michael Lampis
fonte