Complejidad parametrizada - Parameterized complexity

En informática , la complejidad parametrizada es una rama de la teoría de la complejidad computacional que se centra en clasificar los problemas computacionales de acuerdo con su dificultad inherente con respecto a múltiples parámetros de la entrada o salida. Luego, la complejidad de un problema se mide en función de esos parámetros. Esto permite la clasificación de problemas NP-difíciles en una escala más fina que en la configuración clásica, donde la complejidad de un problema solo se mide en función del número de bits en la entrada. El primer trabajo sistemático sobre complejidad parametrizada fue realizado por Downey & Fellows (1999) .

Bajo el supuesto de que P ≠ NP , existen muchos problemas naturales que requieren un tiempo de ejecución superpolinomial cuando la complejidad se mide solo en términos del tamaño de entrada, pero que son computables en un tiempo que es polinomial en el tamaño de entrada y exponencial o peor en un tamaño de entrada. parámetro k . Por lo tanto, si k se fija en un valor pequeño y el crecimiento de la función sobre k es relativamente pequeño, estos problemas aún pueden considerarse "manejables" a pesar de su clasificación tradicional como "intratables".

La existencia de algoritmos de resolución eficientes, exactos y deterministas para problemas NP-completo , o NP-hard , se considera improbable, si los parámetros de entrada no son fijos; Todos los algoritmos conocidos de resolución de estos problemas requieren un tiempo exponencial (o al menos superpolinomial) en el tamaño total de la entrada. Sin embargo, algunos problemas pueden resolverse mediante algoritmos que son exponenciales solo en el tamaño de un parámetro fijo, mientras que son polinomiales en el tamaño de la entrada. Dicho algoritmo se denomina algoritmo tratable de parámetros fijos (fpt-), porque el problema se puede resolver de manera eficiente para valores pequeños del parámetro fijo.

Los problemas en los que se fija algún parámetro k se denominan problemas parametrizados. Se dice que un problema parametrizado que permite tal algoritmo fpt es un problema manejable de parámetros fijos y pertenece a la clase FPT , y el nombre temprano de la teoría de la complejidad parametrizada era manejabilidad de parámetros fijos .

Muchos problemas tienen la siguiente forma: dado un objeto xy un entero no negativo k , ¿ tiene x alguna propiedad que dependa de k ? Por ejemplo, para el problema de la cobertura de vértices , el parámetro puede ser el número de vértices en la cobertura. En muchas aplicaciones, por ejemplo cuando se modela la corrección de errores, se puede asumir que el parámetro es "pequeño" en comparación con el tamaño total de entrada. Entonces es un desafío encontrar un algoritmo que sea exponencial solo en k , y no en el tamaño de entrada.

De esta forma, la complejidad parametrizada puede verse como teoría de la complejidad bidimensional . Este concepto se formaliza de la siguiente manera:

Un problema parametrizado es un idioma , donde hay un alfabeto finito. El segundo componente se denomina parámetro del problema.${\ Displaystyle L \ subseteq \ Sigma ^ {*} \ times \ mathbb {N}}$${\ Displaystyle \ Sigma}$

Un problema con parámetros L se fija parámetros manejables si la pregunta “ ?” se puede decidir en tiempo de ejecución , donde f es una función arbitraria que depende solo de k . La clase de complejidad correspondiente se llama FPT .${\ Displaystyle (x, k) \ in L}$${\ Displaystyle f (k) \ cdot | x | ^ {O (1)}}$

Por ejemplo, existe un algoritmo que resuelve el problema de la cobertura de vértices en el tiempo, donde n es el número de vértices yk es el tamaño de la cobertura de vértices. Esto significa que la cobertura de vértices es manejable con parámetros fijos con el tamaño de la solución como parámetro. ${\ Displaystyle O (kn + 1.274 ^ {k})}$

Clases de complejidad

FPT

FPT contiene los problemas tratables de parámetros fijos , que son aquellos que pueden resolverse a tiempo para alguna función computable f . Por lo general, esta función se considera como exponencial simple, pero la definición admite funciones que crecen aún más rápido. Esto es esencial para gran parte de la historia temprana de esta clase. La parte crucial de la definición es excluir funciones de la forma , como . La clase FPL (parámetro fijo lineal) es la clase de problemas que se pueden resolver en el tiempo para alguna función computable f . Por tanto, FPL es una subclase 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 |}$

Un ejemplo es el problema de satisfacebilidad , parametrizado por el número de variables. Una fórmula dada de tamaño m con k variables se puede verificar mediante fuerza bruta en el tiempo . Una cobertura de vértice de tamaño k en una gráfica de orden n se puede encontrar en el tiempo , por lo que este problema también está en FPT. ${\ Displaystyle O (2 ^ {k} m)}$${\ Displaystyle O (2 ^ {k} n)}$

Un ejemplo de un problema que se cree que no está en FPT es la coloración de gráficos parametrizada por el número de colores. Se sabe que el 3-colorante es NP-duro , y un algoritmo para el gráfico de k -colouring en el tiempo para que se ejecute en tiempo polinómico en el tamaño de la entrada. Por lo tanto, si la coloración del gráfico parametrizada por el número de colores estuviera en FPT, entonces P = NP . ${\ Displaystyle f (k) n ^ {O (1)}}$${\ Displaystyle k = 3}$

Hay varias definiciones alternativas de FPT. Por ejemplo, el requisito de tiempo de ejecución se puede reemplazar por . Además, un problema parametrizado está en FPT si tiene un llamado kernel. La kernelización es una técnica de preprocesamiento que reduce la instancia original a su "núcleo duro", una instancia posiblemente mucho más pequeña que es equivalente a la instancia original pero tiene un tamaño que está limitado por una función en el parámetro. ${\ Displaystyle f (k) + | x | ^ {O (1)}}$

FPT se cierra bajo una reducción parametrizada llamada fpt-reducción , que preserva simultáneamente el tamaño de la instancia y el parámetro.

Obviamente, FPT contiene todos los problemas computables de tiempo polinómico. Además, contiene todos los problemas de optimización en NP que permiten un esquema de aproximación en tiempo polinómico eficiente (EPTAS) .

Jerarquía W

La jerarquía W es una colección de clases de complejidad computacional. Un problema parametrizado está en la clase W [ i ], si cada instancia puede ser transformada (en tiempo fpt) a un circuito combinatorio que tiene trama como máximo i , tal que si y solo si hay una asignación satisfactoria a las entradas que asigna 1 a exactamente k entradas. La trama es el mayor número de unidades lógicas con abanico ilimitado en cualquier camino desde una entrada a la salida. El número total de unidades lógicas en las rutas (conocido como profundidad) debe estar limitado por una constante que se mantenga para todas las instancias del problema. ${\ Displaystyle (x, k)}$${\ Displaystyle (x, k) \ in L}$

Tenga en cuenta eso y para todos . Las clases en la jerarquía W también se cierran bajo fpt-reducción. ${\ Displaystyle {\ mathsf {FPT}} = W [0]}$${\ Displaystyle W [i] \ subseteq W [j]}$${\ Displaystyle i \ leq j}$

Muchos problemas computacionales naturales ocupan los niveles inferiores, W [1] y W [2].

W [1]

Ejemplos de problemas con W [1] -completo incluyen

• decidir si un gráfico dado contiene una camarilla de tamaño k
• decidir si un gráfico dado contiene un conjunto independiente de tamaño k
• decidir si una máquina de Turing de cinta única no determinista determinada acepta dentro de k pasos (problema de "aceptación de máquina de Turing corta"). Esto también se aplica a las máquinas de Turing no deterministas con cintas f ( k ) e incluso cintas f ( k ) de f ( k ) -dimensionales, pero incluso con esta extensión, la restricción al tamaño del alfabeto de la cinta f ( k ) es manejable con parámetros fijos. Fundamentalmente, se permite que la ramificación de la máquina de Turing en cada paso dependa de n , el tamaño de la entrada. De esta forma, la máquina de Turing puede explorar n rutas de cálculo ^{O ( k )} .

W [2]

Ejemplos de problemas con W [2] -completo incluyen

• decidir si un gráfico dado contiene un conjunto dominante de tamaño k
• decidir si una máquina de Turing de varias cintas no determinista determinada acepta en k pasos (problema de "aceptación de la máquina de Turing de varias cintas cortas"). Fundamentalmente, se permite que la ramificación dependa de n (como la variante W [1]), al igual que el número de cintas. Una formulación alternativa W [2] completa sólo permite máquinas de Turing de una sola cinta, pero el tamaño del alfabeto puede depender de n .

W [ t ]

${\ Displaystyle W [t]}$se puede definir usando la familia de problemas de SAT Weighted Weft- t -Depth- d para : es la clase de problemas parametrizados que fpt-reduce a este problema, y . ${\ Displaystyle d \ geq t}$${\ Displaystyle W [t, d]}$${\ Displaystyle W [t] = \ bigcup _ {d \ geq t} W [t, d]}$

Aquí, Weighted Weft- t -Depth- d SAT es el siguiente problema:

• Entrada: Una fórmula booleana de profundidad como máximo d y trama como máximo t , y un número k . La profundidad es el número máximo de puertas en cualquier camino desde la raíz hasta una hoja, y la trama es el número máximo de puertas de abanico en al menos tres en cualquier camino desde la raíz a la hoja.
• Pregunta: ¿Tiene la fórmula una asignación satisfactoria de peso Hamming exactamente k ?

Se puede demostrar que para el problema T- Normalizar ponderado, el SAT está completo para reducciones inferiores a fpt. Aquí, Weighted t -Normalize SAT es el siguiente problema: ${\ Displaystyle t \ geq 2}$${\ Displaystyle W [t]}$

• Entrada: Una fórmula booleana de profundidad como máximo t con una puerta Y en la parte superior y un número k .
• Pregunta: ¿Tiene la fórmula una asignación satisfactoria de peso Hamming exactamente k ?

W [ P ]

W [ P ] es la clase de problemas que pueden ser decididos por una máquina de Turing de tiempo no determinista que hace, como máximo, elecciones no deterministas en el cálculo de (una máquina de Turing restringida por k ). Flum y Grohe (2006)${\ Displaystyle h (k) \ cdot {| x |} ^ {O (1)}}$${\ Displaystyle O (f (k) \ cdot \ log n)}$${\ Displaystyle (x, k)}$

Se sabe que FPT está contenido en W [P] y se cree que la inclusión es estricta. Sin embargo, resolver este problema implicaría una solución al problema de P versus NP .

Otras conexiones con la complejidad computacional no parametrizada son que FPT es igual a W [ P ] si y solo si la satisfacibilidad del circuito se puede decidir a tiempo , o si y solo si hay una función f computable, no decreciente e ilimitada tal que todos los lenguajes reconocidos por un polinomio no determinista máquina de Turing-tiempo usando opciones no deterministas están en  P . ${\ Displaystyle \ exp (o (n)) m ^ {O (1)}}$${\ Displaystyle f (n) \ log n}$

W [ P ] se puede considerar vagamente como la clase de problemas en los que tenemos un conjunto S de n elementos, y queremos encontrar un subconjunto de tamaño k tal que se cumpla una determinada propiedad. Podemos codificar una elección como una lista de k enteros, almacenados en binario. Dado que el valor más alto de cualquiera de estos números es n , se necesitan bits para cada número. Por lo tanto, se necesitan bits totales para codificar una elección. Por lo tanto, podemos seleccionar un subconjunto con opciones no deterministas. ${\ Displaystyle T \ subconjunto S}$${\ Displaystyle \ lceil \ log _ {2} n \ rceil}$${\ Displaystyle k \ cdot \ lceil \ log _ {2} n \ rceil}$${\ Displaystyle T \ subconjunto S}$${\ Displaystyle O (k \ cdot \ log n)}$

XP

XP es la clase de problemas parametrizados que pueden resolverse a tiempo para alguna función computable f . Estos problemas se denominan polinomios por cortes , en el sentido de que cada "corte" de k fijo tiene un algoritmo polinomial, aunque posiblemente con un exponente diferente para cada k. Compare esto con FPT, que simplemente permite un prefactor constante diferente para cada valor de k. XP contiene FPT, y se sabe que esta contención es estricta por diagonalización. ${\ Displaystyle n ^ {f (k)}}$

para-NP

para-NP es la clase de problemas parametrizados que pueden resolverse mediante un algoritmo no determinista a tiempo para alguna función computable f . Se sabe que si y solo si . ${\ Displaystyle f (k) \ cdot | x | ^ {O (1)}}$${\ displaystyle {\ textsf {FPT}} = {\ textsf {para-NP}}}$${\ Displaystyle {\ textsf {P}} = {\ textsf {NP}}}$

Un problema es para-NP-difícil si ya lo es para un valor constante del parámetro. Es decir, hay un "segmento" de k fijo que es -duro. Un problema parametrizado que es -hard no puede pertenecer a la clase , a menos que . Un ejemplo clásico de un problema con parámetros difíciles es la coloración de gráficos , parametrizada por el número k de colores, que ya es difícil (ver Coloración de gráficos # Complejidad computacional ). ${\ displaystyle {\ textsf {NP}}}$${\ displaystyle {\ textsf {NP}}}$${\ displaystyle {\ textsf {para-NP}}}$${\ displaystyle {\ textsf {XP}}}$${\ Displaystyle {\ textsf {P}} = {\ textsf {NP}}}$${\ displaystyle {\ textsf {para-NP}}}$${\ displaystyle {\ textsf {NP}}}$${\ Displaystyle k = 3}$

Una jerarquía

La jerarquía A es una colección de clases de complejidad computacional similar a la jerarquía W. Sin embargo, mientras que la jerarquía W es una jerarquía contenida en NP, la jerarquía A imita más de cerca la jerarquía de tiempo polinómico de la complejidad clásica. Se sabe que se cumple A [1] = W [1].

Notas

Referencias

• Chen, Jianer; Kanj, Iyad A .; Xia, Ge (2006). Límites superiores parametrizados mejorados para cobertura de vértice . MFCS 2006 . Apuntes de conferencias en informática. 4162 . págs. 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 . Saltador. pag. 555. ISBN 978-3-319-21274-6.
• Downey, Rod G .; Becarios, Michael R. (1999). Complejidad parametrizada . Saltador. ISBN 978-0-387-94883-6.
• Flum, Jörg ; Grohe, Martin (2006). Teoría de la complejidad parametrizada . Saltador. ISBN 978-3-540-29952-3.
• Fomin, Fedor V .; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019). Kernelización: teoría del preprocesamiento parametrizado . Prensa de la Universidad de Cambridge. pag. 528. doi : 10.1017 / 9781107415157 . ISBN 978-1107057760.
• Niedermeier, Rolf (2006). Invitación a algoritmos de parámetros fijos . Prensa de la Universidad de Oxford. ISBN 978-0-19-856607-6. Archivado desde el original el 24 de septiembre de 2008.
• Grohe, Martin (1999). "Complejidad descriptiva y parametrizada". Lógica informática . Apuntes de conferencias en informática. 1683 . Springer Berlín Heidelberg. págs. 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. Volumen 51, Números 1 y 3 (2008). The Computer Journal . Número especial doble sobre complejidad parametrizada con 15 artículos de encuestas, reseña de un libro y un prólogo de los editores invitados R. Downey, M. Fellows y M. Langston.

enlaces externos

• Wiki sobre complejidad parametrizada
• Compendio de problemas parametrizados