Há uma NP-difícil problema para o qual não Fixa Parâmetros Tratável algoritmo existe?

Question

Pergunta

Há uma NP-difícil problema para o qual podemos adicionar um parâmetro¹ para criar um "natural"² parametrised problema para o qual não FPT algoritmo existe?

1. A adição de um parâmetro é necessário porque um NP-hard problema é normalmente apenas uma pergunta com uma resposta sim ou não, se você deseja limitar algumas parâmetro, você precisa especificar qual (ainda que algo como $k$-A coloração pode ter uma óbvia, já), assim com "especificando o parâmetro" um deles é a limitação, é "a adição de um parâmetro" para o problema.Uma descrição mais detalhada é incluída na resposta Discreta Lagarto.
2. Eu acho Natural tenta excluir "trivial" de parametrizações, como eu discuti no meu primeiro dúvidas quanto a essa questão.Novamente uma descrição mais detalhada é incluída na resposta Discreta Lagarto.

Dúvida

0. Pode ser uma questão trivial, como talvez, é possível, para sempre "coisas" todo o problema dentro do $f(k_1,k_2,..,k_m)$ parte do $f(k_1,k_2,..,k_m)n^c$ algoritmo, enquanto a definição de $n=c'$ onde $c'$ é uma constante arbitrária.Mas, talvez, a definição exata da FPT impede tal (ab)uso do conceito da FPT.

Com base no comentário do plop há, de fato, existe uma maneira trivial para parametrizar "qualquer" (eu suponho que qualquer devidamente bem colocados problema) problema, de tal forma que a sua parametrização é fpt.Essas parametrizações usar línguas, que eu suponho ser o que é descrito aqui.Um tal de "trivial" (na luz da questão, à luz de dificuldade) parametrização destina-se a ser ignorado.Assim, em "palavras" de Discretos lagarto:não-trivial parâmetro faixa(s) é(são) que se destina.

Answer 1

Você tem que ter um pouco de cuidado com sua pergunta aqui.Note que um NP-hard problema é um problema de decisão, enquanto que a FPT algoritmos de resolver parametrizando decisão ou problemas de pesquisa.Portanto, a questão é um pouco mal formados.No entanto, eu acho que a pergunta que você provavelmente destinado a fazer é:

Há uma NP-difícil problema para o qual podemos adicionar um parâmetro¹ para criar um "natural"² parametrised problema para o qual não FPT algoritmo existe?

Ao que a resposta é (incondicionalmente!) sim.

Primeiro de tudo, notar que a FPT, a classe de problemas que podem ser resolvidos através de um parâmetro fixo tratável algoritmo é um bom subconjunto do XP, a classe de "slice-sábio polinomial" parametrizado problemas que podem ser resolvidos por um algoritmo em tempo polinomial se o parâmetro é fixo.Em outras palavras: $\mathrm{FPT} \subsetneq \mathrm{XP}$.(Devo confessar que eu não sou capaz de fornecer a prova por "padrão diagonalization", que a fonte oferece como única justificação.Talvez uma complexidade teórico pode me ajudar aqui)

Seguinte, observe que, desde, pelo menos, um problema no XP não podem ser resolvidos por uma FPT-algoritmo, qualquer XP-duro (no sentido da FPT-reduções) de problema não pode ser resolvido por uma FPT-algoritmo.

No capítulo "Provable Ignorância:A Classe XP" em Downey e Fellows' Fundamentos de Complexidade Parametrizada, eles completam o argumento mostrando que o que eles chamam de o SEIXO JOGO DE PROBLEMA é XP-dura "interpretando" um problema que é conhecido para ser, pelo menos, PSPACE-rígido (depois de "remover o parâmetro"), então certamente NP-difícil.Ver que há um capítulo do livro para mais detalhes.

---

Deixe-me acrescentar que este resultado foi muito surpreendente para mim, porque para a maioria dos prática problemas, que exigem al tipos de conjecturas ($P eq NP$, A ETH, SETH, 3-SOMA, etc.), mas este resultado é um fato real que é independente de qualquer conjetura.

---

_{1:Para esclarecer, por "a adição de um parâmetro", quero dizer, dado um NP-difícil problema $L\subseteq \Sigma^*$, definir um problema parametrizando $L'\subseteq \Sigma^* imes \mathbb{N}$ como $L':= \{\langle x, k angle \meados de f(x)=k\}$ para alguns função $f :\Sigma^* ightarrow \mathbb{N}$.Este capta a idéia intuitiva de que o parâmetro adicional de medidas de uma propriedade de entrada.
2:A definição em 1 permite ainda que todos os tipos de estranho parametrizações com funções como $f(x)\equiv 1$.Idealmente, gostaríamos de exigir $f$ para medir algo significativo sobre a instância, mas que parece difícil de formalizar.Eu não conseguia pensar em qualquer outra formalização que remove todos os "não-natural" de parametrizações, qualquer um.Então, eu em vez disso, copie o informal noção de "natural parametrizada problemas" a partir de Downey e Fellows " do livro.}

Answer 2

Eu diria que sim, mas você precisa aceitar a condição de que P $ eq$ NP.Tomar $k$-Coloração, onde queremos determinar se um grafo pode ser colorido com $k$ cores tal que quaisquer dois vértices conectados não têm a mesma cor.Claramente, pode-se reduzir 3-para Colorir $k$-a coloração.

Suponha que $k$-A coloração é na FPT, então existe um algoritmo que resolve este problema $f(k) \cdot n^{S(1)}$.Se temos um conjunto de $k = 3$, e , em seguida, obtemos um algoritmo em tempo polinomial, e, portanto, 3-Coloração pode ser resolvido em tempo polinomial, a menos que P $ eq$ NP.Obviamente, se P $ eq$ NP, então não há FPT algoritmo para $k$-A coloração.

Se você está procurando algo mais estritamente no sentido de que ele absolutamente não pode existir, então eu não tenho certeza se como um problema foi encontrado.

Answer 3

Talvez uma outra opção, muito mais fraco do que STanja solução Discreta e lagartos solução, assumindo a hipótese de tempo exponencial (ETH).A ETH assume $FPT eq W[1]$ (Ou apenas assumir a FPT $ eq$ W[1] diretamente).

Assim, com a FPT $ eq$ W[1] supõe-se não (não trivial) parametrização $K-D$ de um W[1]-o grande problema da FPT.Um exemplo de um w[1] problema difícil, que é NP-difícil* é $k-panelinha$, então existe um w[1]-problema difícil, que é NP-difícil problema.Uma vez que (não trivial) parametrização $K-D$ w[1]-problemas difíceis não são (em) a fpt com o pressuposto da FPT $ eq$ W[1], isso significa que, qualquer (não trivial) parametrização $K-D$ de NP-difícil problema $k-Panelinha$ não é FPT.Isso significa que, se a FPT $ eq$ W[1], existe uma NP-difícil problema que não é da FPT.

• O problema de decisão ($k$)-clique é NP-completo, portanto , ele também é NP-difícil como a imagem abaixo mostra:

Isenção de responsabilidade

Eu não vim com esse argumento, ele é basicamente o comentário de Discretos lagarto, e é quase como responder a pergunta:"não $a$ existe?", com:"Eu suponho que $b$ existe, oh lá vem a ser uma $a$ que é no conjunto de $b$, e desde que eu assumi $b$ existe, então deve também existir um $a$, então, sim, existe uma $a$.(como também é explicado pela Discreta lagarto nos comentários)