Complexidade parametrizada - Parameterized complexity

Na ciência da computação , a complexidade parametrizada é um ramo da teoria da complexidade computacional que se concentra na classificação de problemas computacionais de acordo com sua dificuldade inerente com relação a vários parâmetros de entrada ou saída. A complexidade de um problema é então medida em função desses parâmetros. Isso permite a classificação de problemas NP-difíceis em uma escala mais precisa do que no cenário clássico, onde a complexidade de um problema é medida apenas como uma função do número de bits na entrada. O primeiro trabalho sistemático sobre complexidade parametrizada foi feito por Downey & Fellows (1999) .

Partindo do pressuposto de que P ≠ NP , existem muitos problemas naturais que requerem tempo de execução superpolinomial quando a complexidade é medida em termos de tamanho de entrada apenas, mas que são computáveis em um tempo que é polinomial no tamanho de entrada e exponencial ou pior em um parâmetro $k$ . Portanto, se $k$ for fixado em um valor pequeno e o crescimento da função sobre $k$ for relativamente pequeno, esses problemas ainda podem ser considerados "tratáveis", apesar de sua classificação tradicional como "intratáveis".

A existência de algoritmos de solução eficientes, exatos e determinísticos para problemas NP-completos ou de outra forma NP-difíceis é considerada improvável, se os parâmetros de entrada não forem fixos; todos os algoritmos de resolução conhecidos para esses problemas requerem um tempo que é exponencial (ou pelo menos superpolinomial) no tamanho total da entrada. No entanto, alguns problemas podem ser resolvidos por algoritmos que são exponenciais apenas no tamanho de um parâmetro fixo, enquanto polinomiais no tamanho da entrada. Esse algoritmo é chamado de algoritmo tratável de parâmetro fixo (fpt-), porque o problema pode ser resolvido de forma eficiente para pequenos valores do parâmetro fixo.

Problemas em que algum parâmetro $k$ é corrigido são chamados de problemas parametrizados. Um problema parametrizado que permite tal algoritmo fpt é considerado um problema tratável de parâmetro fixo e pertence à classe FPT , e o nome inicial da teoria da complexidade parametrizada era tratabilidade de parâmetro fixo .

Muitos problemas têm a seguinte forma: dado um objeto $xe$ um inteiro não negativo $k$ , $x$ tem alguma propriedade que depende de $k$ ? Por exemplo, para o problema de cobertura de vértices , o parâmetro pode ser o número de vértices na cobertura. Em muitas aplicações, por exemplo, ao modelar a correção de erros, pode-se supor que o parâmetro seja "pequeno" em comparação com o tamanho total da entrada. Então é um desafio encontrar um algoritmo que seja exponencial apenas em $k$ , e não no tamanho de entrada.

Dessa forma, a complexidade parametrizada pode ser vista como uma teoria da complexidade bidimensional . Este conceito é formalizado da seguinte forma:

Um problema parametrizado é uma linguagem , onde existe um alfabeto finito. O segundo componente é chamado de parâmetro do problema.

{\ displaystyle L \ subseteq \ Sigma ^ {*} \ times \ mathbb {N}}

{\ displaystyle \ Sigma}

Um problema parametrizado

L

é tratável de parâmetro fixo se a pergunta " ?" pode ser decidido em tempo de execução , onde

f

é uma função arbitrária dependente apenas de

k

. A classe de complexidade correspondente é chamada de FPT .

{\ displaystyle (x, k) \ em L}

{\ displaystyle f (k) \ cdot | x | ^ {O (1)}}

Por exemplo, existe um algoritmo que resolve o problema da cobertura do vértice no tempo, onde $n$ é o número de vértices $ek$ é o tamanho da cobertura do vértice. Isso significa que a cobertura do vértice é tratável por parâmetros fixos com o tamanho da solução como parâmetro. ${\ displaystyle O (kn + 1,274 ^ {k})}$

Classes de complexidade

FPT

FPT contém os problemas tratáveis de parâmetros fixos , que são aqueles que podem ser resolvidos a tempo por alguma função computável $f$ . Normalmente, essa função é considerada exponencial única, como, por exemplo, mas a definição admite funções que crescem ainda mais rápido. 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 . A classe FPL (parâmetro fixo linear) é a classe de problemas solucionáveis no tempo para alguma função computável $f$ . FPL é, portanto, uma subclasse de FPT. ${\ displaystyle f (k) \ cdot {| x |} ^ {O (1)}}$ ${\ displaystyle 2 ^ {O (k)}}$ ${\ displaystyle f (n, k)}$ ${\ displaystyle n ^ {k}}$ ${\ displaystyle f (k) \ cdot | x |}$

Um exemplo é o problema de satisfatibilidade , parametrizado pelo número de variáveis. Uma dada fórmula de tamanho $m$ com $k$ variáveis pode ser verificada pela força bruta no tempo . Uma cobertura de vértice de tamanho $k$ em um gráfico de ordem $n$ pode ser encontrada no tempo , então esse problema também está em FPT. ${\ displaystyle O (2 ^ {k} m)}$ ${\ displaystyle O (2 ^ {k} n)}$

Um exemplo de um problema que se pensa não estar no FPT é a coloração do gráfico parametrizada pelo número de cores. Sabe-se que a 3-coloração é NP-difícil , e um algoritmo para grafo $k-$ coloração no tempo para seria executado em tempo polinomial no tamanho da entrada. Assim, se a coloração do gráfico parametrizada pelo número de cores estivesse em FPT, então P = NP . ${\ displaystyle f (k) n ^ {O (1)}}$ ${\ displaystyle k = 3}$

Existem várias definições alternativas de FPT. Por exemplo, o requisito de tempo de execução pode ser substituído por . Além disso, um problema parametrizado está no FPT se ele tiver um kernel denominado. Kernelization é uma técnica de pré-processamento que reduz a instância original ao seu "kernel rígido", uma instância possivelmente muito menor que é equivalente à instância original, mas tem um tamanho que é limitado por uma função no parâmetro. ${\ displaystyle f (k) + | x | ^ {O (1)}}$

FPT é fechado sob uma redução parametrizada chamada fpt-redução , que preserva simultaneamente o tamanho da instância e o parâmetro.

Obviamente, o FPT contém todos os problemas computáveis em tempo polinomial. Além disso, contém todos os problemas de otimização em NP que permitem um eficiente esquema de aproximação em tempo polinomial (EPTAS) .

Hierarquia W

A hierarquia W é uma coleção de classes de complexidade computacional. Um problema parametrizado está na classe W [ i ], se cada instância pode ser transformada (em tempo fpt) em um circuito combinatório que tem trama no máximo i , de modo que se e somente se houver uma atribuição satisfatória para as entradas que atribui 1 a exatamente k entradas. A trama é o maior número de unidades lógicas com fan-in ilimitado em qualquer caminho de uma entrada para a saída. O número total de unidades lógicas nos caminhos (conhecido como profundidade) deve ser limitado por uma constante válida para todas as instâncias do problema. ${\ displaystyle (x, k)}$ ${\ displaystyle (x, k) \ em L}$

Observe isso e para todos . As classes na hierarquia W também são fechadas sob redução fpt. ${\ displaystyle {\ mathsf {FPT}} = W [0]}$ ${\ displaystyle W [i] \ subseteq W [j]}$ ${\ displaystyle i \ leq j}$

Muitos problemas computacionais naturais ocupam os níveis inferiores, W [1] e W [2].

W [1]

Exemplos de problemas W [1] -completos incluem

decidir se um dado grafo contém um clique de tamanho k
decidir se um dado gráfico contém um conjunto independente de tamanho k
decidir se uma dada máquina de Turing de fita única não determinística aceita dentro de k passos (problema de "aceitação curta da máquina de Turing"). Isso também se aplica a máquinas de Turing não determinísticas com fitas f ( k ) e até mesmo f ( k ) de fitas f ( k ) -dimensionais, mas mesmo com essa extensão, a restrição ao tamanho do alfabeto da fita f ( k ) é tratável por parâmetro fixo. Crucialmente, a ramificação da máquina de Turing em cada etapa pode depender de n , o tamanho da entrada. Desta forma, a máquina de Turing pode explorar n caminhos de computação ^{O ( k )} .

W [2]

Exemplos de problemas W [2] -completos incluem

decidir se um determinado gráfico contém um conjunto dominante de tamanho k
decidir se uma dada máquina de Turing multi-fitas não determinística aceita dentro de k etapas (problema de "aceitação da máquina de Turing multi-fitas curta"). Crucialmente, a ramificação pode depender de n (como a variante W [1]), assim como o número de fitas. Uma formulação alternativa completa W [2] permite apenas máquinas de Turing de fita única, mas o tamanho do alfabeto pode depender de n .

W [ t ]

${\ displaystyle W [t]}$ pode ser definido usando a família de problemas Weighted Weft- $t$ -Depth- $d$ SAT para : é a classe de problemas parametrizados que fpt-reduz a este problema, e . ${\ displaystyle d \ geq t}$ ${\ displaystyle W [t, d]}$ ${\ displaystyle W [t] = \ bigcup _ {d \ geq t} W [t, d]}$

Aqui, Weighted Weft- $t$ -Depth- $d$ SAT é o seguinte problema:

Entrada: Uma fórmula booleana de profundidade no máximo $d$ e trama no máximo $t$ , e um número $k$ . A profundidade é o número máximo de portas em qualquer caminho da raiz a uma folha, e a trama é o número máximo de portas de leque em pelo menos três em qualquer caminho da raiz a uma folha.
Pergunta: A fórmula tem uma atribuição satisfatória de peso de Hamming exatamente $k$ ?

Pode ser mostrado que para o problema Weighted $t$ -Normalize SAT está completo para sub-reduções de fpt . Aqui, Weighted $t$ -Normalize SAT é o seguinte problema: ${\ displaystyle t \ geq 2}$ ${\ displaystyle W [t]}$

Entrada: Uma fórmula booleana de profundidade no máximo $t$ com uma porta AND no topo e um número $k$ .
Pergunta: A fórmula tem uma atribuição satisfatória de peso de Hamming exatamente $k$ ?

W [ P ]

W [ P ] é a classe de problemas que pode ser decidida por uma máquina de Turing não-determinística que faz no máximo escolhas não-determinísticas na computação em (uma máquina de Turing restrita a k ). Flum & Grohe (2006) ${\ displaystyle h (k) \ cdot {| x |} ^ {O (1)}}$ ${\ displaystyle O (f (k) \ cdot \ log n)}$ ${\ displaystyle (x, k)}$

Sabe-se que o FPT está contido em W [P] e acredita-se que a inclusão seja estrita. No entanto, resolver esse problema implicaria em uma solução para o problema P versus NP .

Outras conexões com a complexidade computacional não parametrizada são que FPT é igual a W [ P ] se e somente se a satisfatibilidade do circuito pode ser decidida no tempo , ou se e somente se houver uma função computável, não decrescente e ilimitada f tal que todas as linguagens reconhecidas por um polinômio não determinístico -tempo de Turing máquina utilizando escolhas nondeterministic estão em P . ${\ displaystyle \ exp (o (n)) m ^ {O (1)}}$ ${\ displaystyle f (n) \ log n}$

W [ P ] pode ser vagamente pensado como a classe de problemas em que temos um conjunto $S$ de $n$ itens e queremos encontrar um subconjunto de tamanho $k$ tal que uma certa propriedade seja mantida. Podemos codificar uma escolha como uma lista de $k$ inteiros, armazenados em binário. Uma vez que o maior que qualquer um desses números pode ser é $n$ , os bits são necessários para cada número. Portanto, o total de bits é necessário para codificar uma escolha. Portanto, podemos selecionar um subconjunto com escolhas não determinísticas. ${\ displaystyle T \ subset S}$ ${\ displaystyle \ lceil \ log _ {2} n \ rceil}$ ${\ displaystyle k \ cdot \ lceil \ log _ {2} n \ rceil}$ ${\ displaystyle T \ subset S}$ ${\ displaystyle O (k \ cdot \ log n)}$

XP

XP é a classe de problemas parametrizados que podem ser resolvidos a tempo por alguma função computável $f$ . Esses problemas são chamados de polinômios em fatias , no sentido de que cada "fatia" de k fixo tem um algoritmo polinomial, embora possivelmente com um expoente diferente para cada k. Compare isso com FPT, que apenas permite um prefator constante diferente para cada valor de k. XP contém FPT e sabe-se que essa contenção é estrita por diagonalização. ${\ displaystyle n ^ {f (k)}}$

para-NP

para-NP é a classe de problemas parametrizados que podem ser resolvidos por um algoritmo não determinístico a tempo para alguma função computável $f$ . Sabe-se que se e somente se . ${\ displaystyle f (k) \ cdot | x | ^ {O (1)}}$ ${\ displaystyle {\ textf {FPT}} = {\ textf {para-NP}}}$ ${\ displaystyle {\ textf {P}} = {\ textf {NP}}}$

Um problema é para-NP-difícil se já for -difícil para um valor constante do parâmetro. Ou seja, existe uma "fatia" de $k$ fixo que é -dure. Um problema parametrizado que é -hard não pode pertencer à classe , a menos que . Um exemplo clássico de um problema parametrizado -hard é a coloração do gráfico , parametrizada pelo número $k$ de cores, que já é -difícil (veja Coloração do gráfico # Complexidade computacional ). ${\ displaystyle {\ textf {NP}}}$ ${\ displaystyle {\ textf {NP}}}$ ${\ displaystyle {\ textf {para-NP}}}$ ${\ displaystyle {\ textf {XP}}}$ ${\ displaystyle {\ textf {P}} = {\ textf {NP}}}$ ${\ displaystyle {\ textf {para-NP}}}$ ${\ displaystyle {\ textf {NP}}}$ ${\ displaystyle k = 3}$

Uma hierarquia

A hierarquia A é uma coleção de classes de complexidade computacional semelhantes à hierarquia W. No entanto, enquanto a hierarquia W é uma hierarquia contida em NP, a hierarquia A imita mais de perto a hierarquia de tempo polinomial da complexidade clássica. É sabido que A [1] = W [1] é válido.

Notas

^ Chen, Kanj e Xia 2006
^ Grohe (1999)
^ Buss, Jonathan F, Islam, Tarique (2006). “Simplificando a hierarquia da trama” . Ciência da Computação Teórica . 351 (3): 303–313. doi : 10.1016 / j.tcs.2005.10.002 .CS1 maint: vários nomes: lista de autores ( link )
^ Flum & Grohe , p. 39

Referências

Chen, Jianer; Kanj, Iyad A .; Xia, Ge (2006). Limites superiores parametrizados aprimorados para cobertura de vértices . MFCS 2006 . Notas de aula em Ciência da Computação. 4162 . pp. 238–249. CiteSeerX 10.1.1.432.831 . doi : 10.1007 / 11821069_21 . ISBN 978-3-540-37791-7.
Cygan, Marek; Fomin, Fedor V .; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Algoritmos parametrizados . Springer. p. 555. ISBN 978-3-319-21274-6.
Downey, Rod G .; Fellows, Michael R. (1999). Complexidade parametrizada . Springer. ISBN 978-0-387-94883-6.
Flum, Jörg ; Grohe, Martin (2006). Teoria da Complexidade Parametrizada . Springer. ISBN 978-3-540-29952-3.
Fomin, Fedor V .; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019). Kernelization: Theory of Parameterized Preprocessing . Cambridge University Press. p. 528. doi : 10.1017 / 9781107415157 . ISBN 978-1107057760.
Niedermeier, Rolf (2006). Convite para algoritmos de parâmetros fixos . Imprensa da Universidade de Oxford. ISBN 978-0-19-856607-6. Arquivado do original em 24/09/2008.
Grohe, Martin (1999). "Complexidade Descritiva e Parametrizada". Lógica da ciência da computação . Notas de aula em Ciência da Computação. 1683 . Springer Berlin Heidelberg. pp. 14–31. CiteSeerX 10.1.1.25.9250 . doi : 10.1007 / 3-540-48168-0_3 . ISBN 978-3-540-66536-6.
The Computer Journal. Volume 51, Números 1 e 3 (2008). The Computer Journal . Edição dupla especial sobre complexidade parametrizada com 15 artigos de pesquisa, resenhas de livros e um prefácio dos editores convidados R. Downey, M. Fellows e M. Langston.

links externos

[1] Chen, Kanj e Xia 2006

[2] Grohe (1999)

[3] Buss, Jonathan F, Islam, Tarique (2006). “Simplificando a hierarquia da trama” . Ciência da Computação Teórica . 351 (3): 303–313. doi : 10.1016 / j.tcs.2005.10.002 .CS1 maint: vários nomes: lista de autores ( link )

[FOOTNOTEFlumGrohe39-4] Flum & Grohe , p. 39

Languages

In other projects