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.
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 , é 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. 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].
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.
Respostas:
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.
fonte