Qual é a motivação por trás da definição de rastreabilidade de parâmetros fixos?

O FPT contém os problemas tratáveis do parâmetro fixo, que são aqueles que podem ser resolvidos no tempo para alguma função computável . Normalmente, essa função é considerada exponencial única, como mas a definição admite funções que crescem ainda mais rapidamente. Isso é essencial para grande parte do início da história desta classe. A parte crucial da definição é excluir funções da forma , como . $f(k)\cdot|x|^{O(1)}$ $f$ $2^{O(k)}$ $f(n,k)$ $n^k$

Pergunta : Qual é a motivação por trás dessa definição?

O que me intriga é que, se é fixo (conforme "rastreabilidade de parâmetros fixos"), então é um polinômio em . Então, por que é crucial excluir ? $k$ $n^k$ $n$ $n^k$

cc.complexity-theory fixed-parameter-tractable Douglas S. Stones
fonte

Porque é frequentemente trivial do ponto de vista da teoria e muito lento do ponto de vista prático. Uma maneira de colocar isso é que os negócios do FPT tentam entender a complexidade computacional dos problemas para os valores dos parâmetros que estão no campo de valores de e .

n^{k}

$n^k$

n \approx 1000000

$n ≈ 1000000$

k \approx 30

$k ≈ 30$

Jukka Suomela

Hmm ... então, se eu entendi direito, se deixarmos entrar no FPT, acabaremos incluindo um monte de problemas de decisão trivialmente, através de algoritmos de força bruta.

n^{k}

$n^k$

Douglas S. Stones

Está certo. Claro que há uma hierarquia de problemas com parâmetros fixos, e o FPT está na parte inferior. n ^ k está no topo. De maneira mais geral, a idéia é tentar separar a influência do parâmetro e a influência de e, portanto, as duas partes separadas do tempo de execução.

n

$n$

Suresh Venkat

@JukkaSuomela: Acho que seu comentário pode ser uma resposta.

Suresh Venkat

Respostas:

Se você precisar apenas que a taxa de crescimento seja um polinômio em para fixo , obterá a definição da classe de complexidade parametrizada XP, que certamente é um objeto de interesse, portanto não há nada errado em considerá-la. $n$ $k$

Você obtém a definição de FPT se impuser ainda mais a condição de que o grau do polinômio em permaneça fixo à medida que o parâmetro aumenta. O FPT é uma subclasse particularmente tratável do XP e, intuitivamente, o motivo é que uma expressão como não explode tão rapidamente quanto uma expressão como , se e são ambos $n$ $2^k n^2$ $k^2 n^k$ $k$ $n$ aumentando. Essa intuição é apoiada na prática e na teoria; ou seja, os problemas do FPT tendem a ser notavelmente mais tratáveis na prática do que os problemas arbitrários do XP, e também é possível obter uma boa imagem teórica da estrutura do XP iniciando com o FPT na parte inferior e construindo hierarquias de outras subclasses do XP (como o Hierarquia W) acima dela.

Timothy Chow
fonte