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 la clasificación de los problemas computacionales según su dificultad inherente con respecto a múltiples parámetros de la entrada o la salida. La complejidad de un problema se mide entonces como una función de esos parámetros. Esto permite la clasificación de problemas NP-hard en una escala más fina que en el entorno clásico, donde la complejidad de un problema solo se mide como una 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 la complejidad parametrizada fue realizado por Downey y Fellows (1999).

Suponiendo 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 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-duros se considera improbable 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, superpolinomial) en el tamaño total de la entrada. Sin embargo, algunos problemas se pueden resolver 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. Un algoritmo de este tipo se denomina algoritmo manejable con parámetros fijos (FPT), porque el problema se puede resolver de manera eficiente (es decir, en tiempo polinomial) para valores constantes del parámetro fijo.

Los problemas en los que algún parámetro k es fijo se denominan problemas parametrizados. Un problema parametrizado que permite un algoritmo FPT de este tipo se denomina problema manejable con parámetros fijos y pertenece a la clase FPT , y el nombre inicial de la teoría de la complejidad parametrizada fue manejabilidad con parámetros fijos .

Muchos problemas tienen la siguiente forma: dado un objeto x y un entero no negativo k , ¿ x tiene 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 ser vista como una teoría de la complejidad bidimensional . Este concepto se formaliza de la siguiente manera:

Un problema parametrizado es un lenguaje , donde es un alfabeto finito. El segundo componente se denomina 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 " ?" puede resolverse en tiempo de ejecución , donde f es una función arbitraria que depende únicamente de k . La clase de complejidad correspondiente se denomina FPT . ${\displaystyle (x,k)\in L}$ ${\displaystyle f(k)\cdot |x|^{O(1)}}$

Por ejemplo, existe un algoritmo que resuelve el problema de 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, siendo el tamaño de la solución el parámetro. ${\displaystyle O(kn+1.274^{k})}$

Clases de complejidad

FPT

La FPT contiene los problemas manejables con parámetros fijos , que son aquellos que se pueden resolver a tiempo para alguna función computable f . Normalmente, se piensa que esta función es exponencial simple, como , pero la definición admite funciones que crecen incluso 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 (linear de parámetros fijos) es la clase de problemas resolubles en el tiempo para alguna función computable f . ^[2] FPL es, por tanto, una subclase de FPT. Un ejemplo es el problema de satisfacibilidad booleano , parametrizado por el número de variables. Una fórmula dada de tamaño m con k variables se puede comprobar por fuerza bruta en el tiempo . Una cobertura de vértices de tamaño k en un grafo de orden n se puede encontrar en el tiempo , por lo que el problema de cobertura de vértices 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 de gráficos parametrizada por la cantidad de colores. Se sabe que la coloración 3 es NP-hard y un algoritmo para la coloración de gráficos k en el tiempo para se ejecutaría en tiempo polinomial en el tamaño de la entrada. Por lo tanto, si la coloración de gráficos parametrizada por la cantidad de colores estuviera en FPT, entonces P = NP . ${\displaystyle f(k)n^{O(1)}}$ ${\displaystyle k=3}$

Existen 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 denominado 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 que está limitado por una función en el parámetro. ${\displaystyle f(k)+|x|^{O(1)}}$

La FPT está cerrada bajo una noción parametrizada de reducciones llamadas fpt-reducciones . Dichas reducciones transforman una instancia de algún problema en una instancia equivalente de otro problema (con ) y pueden calcularse en 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 de aproximación en tiempo polinomial eficiente (EPTAS) .

Yojerarquía

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 transformarse (en tiempo fpt) en un circuito combinatorio que tiene trama como máximo 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 un abanico de entrada mayor que dos en cualquier camino desde una entrada a la salida. El número total de unidades lógicas en los caminos (conocido como profundidad) debe estar limitado por una constante que se cumpla para todas las instancias del problema. ${\displaystyle (x,k)}$ ${\displaystyle (x,k)\in L}$

Tenga en cuenta que y para todos . Las clases en la jerarquía W también están cerradas bajo fpt-reduction. ${\displaystyle {\mathsf {FPT}}=W[0]}$ ${\displaystyle W[i]\subseteq W[j]}$ ${\displaystyle i\leq j}$

Un problema completo para W [ i ] es la Satisfacción Normalizada Ponderada i : ^[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 AND y OR), ¿puede satisfacerse estableciendo exactamente k variables en 1? ${\displaystyle i+1}$

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

Yo[1]

Algunos 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 máquina de Turing no determinista de una sola cinta acepta dentro de k pasos (problema de "aceptación de máquina de Turing corta"). Esto también se aplica a máquinas de Turing no deterministas con cintas f ( k ) e incluso f ( k ) de cintas f ( k )-dimensionales, pero incluso con esta extensión, la restricción al tamaño del alfabeto de 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 computación.

Yo[2]

Algunos ejemplos de problemas W [2]-completos incluyen

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

Yo[a]

${\displaystyle W[t]}$se puede definir utilizando la familia de problemas SAT de trama ponderada -t -profundidad- d para : es la clase de problemas parametrizados que fpt-reducen a este problema, y ​​. ${\displaystyle d\geq t}$ ${\displaystyle W[t,d]}$ ${\displaystyle W[t]=\bigcup _{d\geq t}W[t,d]}$

Aquí, la 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 SAT normalizado t ponderado es completo para reducciones fpt inferiores. ^[4] Aquí, SAT normalizado t ponderado 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 ?

Yo[PAG]

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 con restricciones 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 puede decidirse en el tiempo , o si y solo si hay una función f computable, no decreciente y ilimitada tal que todos los lenguajes reconocidos por una máquina de Turing de tiempo polinomial no determinista que usa opciones no deterministas están en  P . ${\displaystyle \exp(o(n))m^{O(1)}}$ ${\displaystyle f(n)\log n}$

W [ P ] puede considerarse libremente 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 números enteros, almacenada en binario. Dado que el mayor valor 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 elecciones 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)}$

XP

XP es la clase de problemas parametrizados que se pueden resolver en el tiempo para alguna función computable f . Estos problemas se denominan polinomios por rebanadas, en el sentido de que cada "rebanada" de k fija tiene un algoritmo polinomial, aunque posiblemente con un exponente diferente para cada k. Compárese 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 se pueden resolver 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 es -difícil para un valor constante del parámetro. Es decir, hay una "porción" de k fija que es -difícil. Un problema parametrizado que es -difícil no puede pertenecer a la clase , a menos que . Un ejemplo clásico de un problema parametrizado -difícil es la coloración de grafos , parametrizada por la cantidad k de colores, que ya es -difícil para (ver Coloración de grafos#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] es válido.

Véase también

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

Notas

1. Chen, Kanj y Xia 2006
2. Grohe (1999)
3. Downey, Rod G.; Fellows, Michael R. (agosto de 1995). "Tratabilidad y completitud de parámetros fijos I: resultados básicos". Revista SIAM de informática . 24 (4): 873–921. doi :10.1137/S0097539792228228. ISSN  0097-5397.
4. Buss, Jonathan F; Islam, Tarique (2006). "Simplificando la jerarquía de la trama". Ciencias Informáticas Teóricas . 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. ; Fellows, Michael R. (1999). Complejidad parametrizada. Springer. ISBN 978-0-387-94883-6.
• Flum, Jörg; Grohe, Martin (2006). Teoría de la complejidad parametrizada. Springer. ISBN 978-3-540-29952-3.
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019). Kernelización: teoría del preprocesamiento parametrizado . Cambridge University Press. pág. 528. doi :10.1017/9781107415157. ISBN . 978-1107057760. Número de identificación del sujeto  263888582.
• Gurevich, Yuri; Stockmeyer, Larry; Vishkin, Uzi (1984). Solución de problemas NP-hard en grafos que son casi árboles y una aplicación a problemas de localización de instalaciones . Revista de la ACM. pág. 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, Martin (1999). "Complejidad descriptiva y parametrizada". Lógica informática . Apuntes de clase sobre informática. Vol. 1683. Springer Berlin 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 doble especial sobre complejidad parametrizada con 15 artículos de investigación, una reseña de libros 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