Complejidad parametrizada

Rama de la teoría de la complejidad computacional

En informática , la complejidad parametrizada es una rama de la teoría de la complejidad computacional que se centra en clasificar problemas computacionales según su dificultad inherente con respecto a múltiples parámetros de 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 el entorno clásico, donde la complejidad de un problema sólo se mide en función del número de bits en la entrada. Esto parece haber sido demostrado por primera vez en Gurevich, Stockmeyer y Vishkin (1984). 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 únicamente en términos del tamaño de entrada, pero que son computables en un tiempo que es polinómico en el tamaño de entrada y exponencial o peor en un 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, entonces tales problemas aún pueden considerarse "tratables" a pesar de su clasificación tradicional como "intratables".

La existencia de algoritmos de resolución eficientes, exactos y deterministas para problemas NP-completos o NP-difíciles se considera poco probable si los parámetros de entrada no son fijos; Todos los algoritmos de resolución conocidos para estos problemas requieren un tiempo exponencial ( en particular superpolinomio) en el tamaño total de la entrada. Sin embargo, algunos problemas pueden resolverse mediante algoritmos que son exponenciales sólo en el tamaño de un parámetro fijo, mientras que polinomiales en el tamaño de la entrada. Este tipo de algoritmo se denomina algoritmo tratable de parámetros fijos (FPT), porque el problema se puede resolver eficientemente (es decir, en tiempo polinómico) para valores constantes del parámetro fijo.

Los problemas en los que algún parámetro k es fijo se denominan problemas parametrizados. Se dice que un problema parametrizado que permite tal algoritmo FPT es un problema tratable de parámetros fijos y pertenece a la clase FPT , y el nombre inicial de la teoría de la complejidad parametrizada fue tratabilidad de parámetros fijos .

Muchos problemas tienen la siguiente forma: dado un objeto x y un entero no negativo k , ¿ tiene x alguna propiedad que dependa de k ? Por ejemplo, para el problema de cobertura de vértices , el parámetro puede ser el número de vértices en la cobertura. En muchas aplicaciones, por ejemplo al modelar la corrección de errores, se puede suponer 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 manera, la complejidad parametrizada puede verse como una teoría de la complejidad bidimensional . Este concepto se formaliza de la siguiente manera:

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

Un problema parametrizado L es manejable con parámetros fijos si la pregunta " ?" se puede decidir en tiempo de ejecución , donde f es una función arbitraria que depende sólo 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, ^[1] donde n es el número de vértices y k 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

FTP

FPT contiene los problemas manejables de parámetros fijos , que son aquellos que pueden resolverse a tiempo para alguna función computable f . Normalmente, esta función se considera exponencial única, como , 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 . ${\displaystyle f(k)\cdot {|x|}^{O(1)}}$ ${\displaystyle 2^{O(k)}}$ ${\displaystyle f(n,k)}$ ${\displaystyle k^{n}}$

La clase FPL (parámetro fijo lineal) es la clase de problemas solucionables en el tiempo para alguna función computable f . ^[2] FPL es, por tanto, una subclase de FPT. Un ejemplo es el problema booleano de satisfacibilidad , parametrizado por el número de variables. Una fórmula dada de tamaño m con k variables puede comprobarse mediante fuerza bruta en el tiempo . Una cobertura de vértice de tamaño k en un gráfico de orden n se puede encontrar en el tiempo , por lo que el problema de cobertura de vértice también está en FPL. ${\displaystyle f(k)\cdot |x|}$ ${\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 del gráfico parametrizada por el número de colores. Se sabe que la coloración 3 es NP-duro , y un algoritmo para la coloración k del gráfico en el tiempo se ejecutaría en tiempo polinomial 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, en FPT existe un problema de parametrización si éste tiene el llamado núcleo. 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 limitado por una función en el parámetro. ${\displaystyle f(k)+|x|^{O(1)}}$

FPT está cerrado bajo una noción parametrizada de reducciones llamadas fpt-reductions . Tales reducciones transforman una instancia de algún problema en una instancia equivalente de otro problema (con ) y se pueden calcular en el tiempo donde es un polinomio. ${\displaystyle (x,k)}$ ${\displaystyle (x',k')}$ ${\displaystyle k'\leq g(k)}$ ${\displaystyle f(k)\cdot p(|x|)}$ ${\displaystyle p}$

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

Jerarquía W

La jerarquía W es una colección de clases de complejidad computacional. Un problema parametrizado es de la clase W [ i ], si cada instancia se puede transformar (en tiempo fpt) en un circuito combinatorio que tenga como máximo una trama i , de modo 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 entrada en abanico mayor que dos en cualquier ruta desde una entrada hasta 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 están cerradas bajo reducción fpt. ${\displaystyle {\mathsf {FPT}}=W[0]}$ ${\displaystyle W[i]\subseteq W[j]}$ ${\displaystyle i\leq j}$

Un problema completo para W [ i ] es la i ponderada - Satisfabilidad normalizada : ^[3] dada una fórmula booleana escrita como un AND de OR de AND de ... de variables posiblemente negadas, con capas de AND u OR (y i alternancias entre Y y O), ¿se puede satisfacer estableciendo exactamente k variables en 1? ${\displaystyle i+1}$

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

W [1]

Ejemplos de problemas W [1] completos 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 determinada máquina de Turing de cinta única no determinista acepta dentro de k pasos (problema de "aceptación corta de la máquina de Turing"). 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 ) dimensiones, 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 manera, la máquina de Turing puede explorar n ^{O( k )} caminos de cálculo.

W [2]

Ejemplos de problemas completos W [2] incluyen

• decidir si un gráfico dado contiene un conjunto dominante de tamaño k
• decidir si una determinada máquina de Turing de cintas múltiples no determinista acepta dentro de k pasos (problema de "aceptación de la máquina de Turing de cintas múltiples 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 permite solo máquinas de Turing de cinta única, pero el tamaño del alfabeto puede depender de n .

W [ t ]

${\displaystyle W[t]}$se puede definir usando la familia de problemas SAT de trama ponderada- t -profundidad- 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í, Trama ponderada- t -Profundidad- 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 entrada en abanico de al menos tres en cualquier camino desde la raíz hasta una hoja.
• Pregunta: ¿Tiene la fórmula una asignación satisfactoria de peso de Hamming exactamente k ?

Se puede demostrar que para el problema Ponderado t -Normalizar SAT está completo para reducciones inferiores a fpt. ^[4] Aquí, Ponderado t -Normalizar 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 AND en la parte superior y un número k .
• Pregunta: ¿Tiene la fórmula una asignación satisfactoria de peso de Hamming exactamente k ?

W [ P ]

W [ P ] es la clase de problemas que pueden resolverse mediante una máquina de Turing de tiempo no determinista que, como máximo, realiza elecciones no deterministas en el cálculo (una máquina de Turing restringida en 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 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 existe una función computable, no decreciente e ilimitada f tal que todos los lenguajes reconocidos por un polinomio no determinista La máquina de Turing en el tiempo que utiliza opciones no deterministas está en  P . ${\displaystyle \exp(o(n))m^{O(1)}}$ ${\displaystyle f(n)\log n}$

W [ P ] puede considerarse en términos generales 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 máximo que puede ser cualquiera de estos números es n , se necesitan bits para cada número. Por lo tanto , se necesita un total de bits para codificar una elección. Por tanto, podemos seleccionar un subconjunto con opciones no deterministas. ${\displaystyle T\subset S}$ ${\displaystyle \lceil \log _{2}n\rceil }$ ${\displaystyle k\cdot \lceil \log _{2}n\rceil }$ ${\displaystyle T\subset S}$ ${\displaystyle O(k\cdot \log n)}$

experiencia

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 "porción" de k fija tiene un algoritmo polinómico, 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 en el tiempo para alguna función computable f . Se sabe que si y sólo si . ^[5] ${\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 una "porción" de k fija que es dura. Un problema parametrizado que sea difícil 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 (consulte 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 polinomial de la complejidad clásica. Se sabe que A[1] = W[1] se cumple.

Ver también

• Algoritmo de aproximación parametrizado , para problemas de optimización, un algoritmo que se ejecute en tiempo FPT podría aproximarse a la solución.

Notas

1. Chen, Kanj y Xia 2006
2. Grohe (1999)
3. Downey, Rod G.; Becarios, Michael R. (agosto de 1995). "Tratabilidad e integridad de parámetros fijos I: resultados básicos". Revista SIAM de Computación . 24 (4): 873–921. doi :10.1137/S0097539792228228. ISSN  0097-5397.
4. Autobús, Jonathan F; Islam, Tarique (2006). "Simplificando la jerarquía de la trama". Informática Teórica . 351 (3): 303–313. doi : 10.1016/j.tcs.2005.10.002 .
5. Flum y Grohe (2006), pág. 39.

Referencias

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). Límites superiores parametrizados mejorados para la cobertura de vértices . Fundamentos matemáticos de la informática. vol. 4162. Berlín, Heidelberg: Springer. 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, Martín (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. S2CID  263888582.
• Gurevich, Yuri; Stockmeyer, Larry; Vishkin, Uzi (1984). Resolución de problemas NP-difíciles en gráficos que son casi árboles y una aplicación a problemas de ubicación de instalaciones . Revista de la ACM. pag. 459-473.
• 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, Martín (1999). "Complejidad Descriptiva y Parametrizada". Lógica informática . Apuntes de conferencias sobre informática. vol. 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.
• La revista informática . Volumen 51, Números 1 y 3 (2008). La revista informática. Número especial doble sobre complejidad parametrizada con 15 artículos de encuesta, reseña de libros y prólogo de los editores invitados R. Downey, M. Fellows y M. Langston.

enlaces externos

• Wiki sobre complejidad parametrizada
• Compendio de Problemas Parametrizados