Conjectura: Todos os idiomas completos do FPT NP são isomorphic de parâmetro fixo

10

Conjectura de Berman-Hartman: todas as linguagens completas de NP são parecidas, no sentido de que podem ser relacionadas entre si por isomorfismos polinomiais no tempo [1].

Estou interessado em uma versão mais refinada do "tempo polinomial", isto é, se usarmos reduções parametrizadas.

Um problema com parâmetros é um subconjunto de , onde Σ é um alfabeto finito e Z 0 é o conjunto de números não negativos. Uma instância de um problema parametrizado é, portanto, um par ( I , k ) , onde k é o parâmetro.Σ×Z0ΣZ0(I,k)k

Um problema com parâmetros é fixa-parâmetro redutível a um problema parametrizada π 2 se existem funções f , g : Z 0 Z 0 , Φ : Σ * x Z 0 Σ * e um polinómio p ( · ) tal que, para qualquer instância ( I , k ) de π 1 , ( Φ ( I ,π1π2fgZ0Z0Φ:Σ×Z0Σp(·)(I,k)π1 é um exemplo de π 2 calculável no tempo f ( k ) · p ( | I | ) e ( I , K ) π 1 , se e somente se ( Φ ( I , K ) , g ( k ) ) ¸ dois(Φ(I,k),g(k))π2f(k)·p(|I|)(I,k)π1(Φ(I,k),g(k))π2. Dois problemas parametrizados são equivalentes em parâmetros fixos se forem redutíveis em parâmetros fixos.

Alguns problemas de NP-completos são FPT, por exemplo, a versão de decisão do problema de cobertura de vértices é NP-Completa, possui um algoritmo [2]. Encontrar melhores reduções de parâmetro fixo de um problema de FPT que é NP-Complete pode levar a um algoritmo melhor, por exemplo, invocando uma redução para uma "versão acima da garantia" do problema Multiway Cut pode levar a um algoritmo no tempo O ( 4 k ) para o problema AGVC (Acima da garantia do vértice) [3], melhor que o algoritmo O ( 15 k ) original [4].O(1.2738k+kn)O(4k)O(15k)

My Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic.

Essa conjectura é verdadeira?

[1] Berman, L .; Hartmanis, J. (1977), "Sobre isomorfismos e densidade de NP e outros conjuntos completos", SIAM Journal on Computing 6 (2): 305–322.

[2] J. Chen, IA Kanj e G. Xia, limites superiores aprimorados para cobertura de vértices, Theor.Comput. Sci., 411 (2010), pp. 3736-3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk e JO Wojtaszczyk, No corte de várias vias parametrizado acima dos limites inferiores, no IPEC, 2011.

[4] M. Mahajan e V. Raman, Parametrizando acima dos valores garantidos: Maxsat e maxcut, J. Algorithms, 31 (1999), pp. 335-354.

Rupei Xu
fonte
3
Não entendo o que você quer dizer com "linguagem completa do FPT NP". Não há noção natural de uma língua sendo ela própria FPT; a questão é se um par de idioma / parâmetro é FPT.
Huck Bennett #
4
Observe que uma redução de parâmetro fixo pode apenas resolver um problema de FPT e gerar uma instância trivial Sim / Não do problema de destino.
Serge Gaspers

Respostas:

7

Serge Gaspers já mencionou por que sua conjectura é trivialmente verdadeira.
No entanto, é possível obter isomorfismos de parâmetros fixos em tempo polinomial ,
que agora percebo que não são muito menos triviais, uma vez que se aplicam a todos os
pares ordenados de problemas não triviais de FPT com uma redução no sentido comum.


cπ1
YNπ2
π1π2

π1nc
YN
π1π2


cπ1knnck Portanto, ele satisfaz sua condição de parâmetro fixo.


fonte