¿Existe un problema NP-difícil para el cual no existe un algoritmo manejable de parámetros fijos?

Question

Pregunta

¿Existe algún problema NP-duro para el cual podamos agregar un parámetro?¹ para crear un "natural"² ¿Problema parametrizado para el cual no existe un algoritmo FPT?

1. Es necesario agregar un parámetro porque un problema NP-difícil normalmente es solo una pregunta con una respuesta de sí o no, si desea limitar algún parámetro debe especificar cuál (aunque sea algo como $k$-Es posible que la coloración ya tenga uno obvio), por lo que al "especificar qué parámetro" se está limitando, se está "agregando un parámetro" al problema.Se incluye una descripción más detallada en la respuesta de Discrete Lizard.
2. Creo que Natural intenta excluir las parametrizaciones "triviales" como lo analizo en mi primera duda en esta pregunta.Nuevamente se incluye una descripción más detallada en la respuesta de Discrete Lizard.

Duda

0. Podría ser una pregunta trivial ya que tal vez sea posible siempre "rellenar" todo el problema dentro del $f(k_1,k_2,..,k_m)$ parte de $f(k_1,k_2,..,k_m)n^c$ algoritmo mientras se configura $n=c'$ dónde $c'$ es una constante arbitraria.Pero tal vez la definición exacta de FPT impida tal (ab)uso del concepto de FPT.

Según el comentario de plop, de hecho existe una forma trivial de parametrizar "cualquier" (supongo que cualquier problema bien planteado) problema, de modo que su parametrización sea fpt.Esas parametrizaciones usan lenguajes, que supongo que son los que se describen. aquí.Se pretende ignorar una parametrización tan "trivial" (a la luz de la pregunta, no de la dificultad).Entonces, en las "palabras" de Lagarto discreto:Se pretende utilizar rangos de parámetros no triviales.

Answer 1

Tienes que ser un poco cuidadoso con tu pregunta aquí. Tenga en cuenta que un problema de NP-DURS es un problema de decisión, mientras que los algoritmos FPT resuelven parametrizados de decisiones o problemas de búsqueda. Así que la pregunta es un poco mal formada. Sin embargo, creo que la pregunta que probablemente pretendías preguntar es:

¿Hay un problema de NP-DURS para el cual podemos agregar un parámetro ^{1 para crear un problema parametrizado "natural" 2 2 2 2 para el que no existe un algoritmo FPT?}

¿A qué respuesta es (incondicionalmente!) sí .

En primer lugar, tenga en cuenta que el FPT, la clase de problemas que son solucionables a través de un algoritmo tráctil parámetro fijo, es un subconjunto adecuado de XP, la clase de problemas parametrizados de "polinomio de forma rebanada" que pueden resolverse mediante un polinomio. - Algoritmo-tiempo si el parámetro está fijo. En otras palabras: $ \ mathrm {ftt} \ subsetnetneq \ mathrm {xp} $ . (Debo confesar que no puedo proporcionar la prueba por "diagonalización estándar" que mi fuente ofrece como la única justificación. Tal vez un teórico de complejidad puede ayudarme aquí)

A continuación, tenga en cuenta que, dado que al menos un problema en XP no se puede resolver mediante un algoritmo FPT, cualquier problema de XP-HARD (en el sentido de las reducciones de FPT) no se puede resolver mediante un algoritmo FPT.

En el capítulo "IntrActabilidad probable: la clase XP" en Downey y Fellows ' Fundamentos de la complejidad parametrizada , completan el argumento mostrando que lo que llaman el problema del juego guijarro es XP-DURO por "reinterpretación" un problema que se sabe que es al menos PSPACE-HARD (después de "quitar el parámetro"), por lo que, sin duda, NP-HARD. Vea que el capítulo del libro para más detalles.

---

Permítanme agregar que este resultado también fue muy sorprendente para mí, porque para la mayoría de los problemas prácticos , necesitamos al tipo de conjeturas ( $ P \ NEQ NP $ , ETH, Seth, 3 Suma, etc.), pero este resultado es un hecho real que es independiente de cualquier conjetura.

---

_{1: Para aclarar, "agregar un parámetro", me refiero a un problema de NP-HARD $ l \ subesteq \ sigma ^ * $ , Defina un problema parametrizado $ l '\ subesteq \ sigma ^ * \ times \ sigma ^ *} $ como $ l':={\ LANGLE X, K \ Rangle \ Mid F (x)= k \ \ \ \ \ N} $ . Esto captura la idea intuitiva de que el parámetro adicional mide una propiedad de la entrada.
2: La definición en 1 aún permite todo tipo de parametrizaciones extrañas con funciones como $ f (x) \ Equiv 1 $ . Idealmente, requeriríamos $ f $ para medir algo significativo sobre la instancia, pero eso parece difícil de formalizar. No podía pensar en ninguna otra formalización que elimine todas las parametrizaciones "antinaturales", tampoco. Por lo tanto, en su lugar, copiaré la noción informal de "problemas parametrizados naturales" del libro de Downey y Fellows.}

Answer 2

Yo diría que sí, pero debe aceptar la condición que p $ \ neq $ np. Tome $ k $ -coloring, donde queremos determinar si una gráfica se puede colorear con $ k $ Los colores de modo que cualquiera de los dos vértices conectados no tengan el mismo color. Claramente, podemos reducir 3 colorantes a $ k $ -coloring.

Supongamos $ k $ -coloring está en FPT, entonces existe un algoritmo que resuelve este problema en $ f ( k) \ cdot n ^ {O (1)} $ . Si establecemos $ k= 3 $ , entonces obtenemos un algoritmo de tiempo polinomial, y por lo tanto 3 colorear se pueden resolver en tiempo de polinomio a menos que p $ \ NEQ $ NP. Obviamente, si P $ \ NEQ $ NP, entonces no hay algoritmo FPT para $ k $ -coloring .

Si está buscando algo más estrictamente en el sentido de que no puede existir, entonces no estoy seguro de si se ha encontrado dicho problema.

Answer 3

Tal vez otra opción, significativamente más débil que la solución de STANJA y las lagartijas discretas, asume la hipótesis de tiempo exponencial (ETH). ETH asume $ FPT \ NEQ W [1] $ (o simplemente asume FPT $ \ NEQ $ W [1] directamente).

Entonces, con FPT $ \ neq $ w [1] uno asume parametrización no (no trivial) $ kd $ de un problema con W [1] -Hard es FPT. Un ejemplo de AW [1] problema duro que es NP-HARD * es $ k-clique $ , por lo que existe un problema de AW [1] -Hard que es un NP - Problema portuario. Dado que (no trivial) parametrización $ kd $ w [1] - Los problemas portuarios no están (en) FPT con el supuesto FPT $ \ neq $ w [1], este medio, cualquier parametrización (no trivial) $ kd $ de NP-Hard Problem $ k-clique $ no es FPT. Eso significa, si FPT $ \ NEQ $ W [1], existe un problema de NP-DURS que no es FPT.

• El problema de la decisión ( $ k $ ) - clique es NP-Complete , por lo tanto, también es NP-HARD ya que la imagen a continuación muestra:

Descargo de responsabilidad

No se le ocurrió este argumento, es básicamente el comentario del lagarto discreto, y es casi como responder la pregunta: "¿Existe $ a $ " con: "Supongo que $ b $ existe, oh, existe que es un $ a $ que está en conjunto $ B $ , y como asumí $ b $ existe, entonces también debe existir una clase $ A $ , por lo que sí, existe un $ a $ . (Como también se explica por lagarto discreto en los comentarios)