Complejidad parametrizada

FPT (tratable con parámetros fijos) es la clase de problemas de decisión decidibles en tiempo determinista.${\displaystyle f(k)\cdot {|x|}^{O(1)}}$donde f es una función computable . Normalmente, se piensa que esta función es una exponencial simple, como por ejemplo:${\displaystyle 2^{O(k)}}$, 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${\displaystyle f(n,k)}$, como${\displaystyle k^{n}}$.

La clase FPL (lineal de parámetros fijos) es la clase de problemas que se pueden resolver en tiempo${\displaystyle f(k)\cdot |x|}$para alguna función computable f . ^{[ 2 ]} FPL es, por lo tanto, una subclase de FPT. Un ejemplo es el problema de satisfacibilidad booleana , parametrizado por el número de variables. Una fórmula dada de tamaño m con k variables puede verificarse por fuerza bruta en tiempo${\displaystyle O(2^{k}m)}$. Una cobertura de vértices de tamaño k en un grafo de orden n se puede encontrar en tiempo${\displaystyle O(2^{k}n)}$, por lo que el problema de cobertura de vértices también está en FPL.

Un ejemplo de un problema que se cree que no está en FPT es la coloración de grafos parametrizada por el número de colores. Se sabe que la 3-coloración es NP-difícil , y un algoritmo para la k- coloración de grafos en tiempo${\displaystyle f(k)n^{O(1)}}$para${\displaystyle k=3}$se ejecutaría en tiempo polinomial en función del tamaño de la entrada. Por lo tanto, si el coloreado de grafos parametrizado por el número de colores estuviera en FPT, entonces P  =  NP .

Hay varias definiciones alternativas de FPT. Por ejemplo, el requisito de tiempo de ejecución puede ser reemplazado por${\displaystyle f(k)+|x|^{O(1)}}$Además, un problema parametrizado pertenece a FPT si posee un 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 original, pero cuyo tamaño está limitado por una función del parámetro.

FPT es cerrado bajo una noción parametrizada de reducciones llamadas reducciones fpt . Decimos que un problema parametrizado${\displaystyle L}$fpt-se reduce a${\displaystyle L'}$Si y solo si existen dos funciones${\displaystyle (x,k)\mapsto x',k\mapsto k'}$, de tal manera que

• ${\displaystyle (x,k)\in L}$si y solo si${\displaystyle (x',k')\in L'}$
• ${\displaystyle (x,k)\mapsto x'}$es en sí mismo un parámetro fijo manejable.
  • Es decir, existe una constante${\displaystyle c}$y una función${\displaystyle k\mapsto k''}$, de tal manera que${\displaystyle (x,k)\mapsto x'}$es computable en tiempo${\displaystyle \leq k''|x|^{c}}$

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 eficiente en tiempo polinomial (EPTAS) .

XP es la clase de problemas parametrizados que se pueden resolver en tiempo${\displaystyle n^{f(k)}}$para alguna función computable f .

Estos problemas se denominan polinomiales por secciones , en el sentido de que cada "sección" de k fijo tiene un algoritmo de tiempo polinomial, aunque con un exponente posiblemente diferente para cada k . Compárese esto con FPT, que simplemente permite un prefactor constante diferente para cada valor de k.

XP contiene estrictamente FPT por diagonalización.

para-NP es la clase de problemas de decisión decidibles en tiempo no determinista.${\displaystyle f(k)\cdot |x|^{O(1)}}$para alguna función computable f .

${\displaystyle {\textsf {FPT}}={\textsf {para-NP}}}$si y solo si${\displaystyle {\textsf {P}}={\textsf {NP}}}$. ^{[ 3 ]}

Un problema es para-NP-difícil si es${\displaystyle {\textsf {NP}}}$-difícil ya para un valor constante del parámetro. Es decir, hay una "porción" de k fijo que es${\displaystyle {\textsf {NP}}}$-difícil. Un problema parametrizado que es${\displaystyle {\textsf {para-NP}}}$-difícil no puede pertenecer a la clase${\displaystyle {\textsf {XP}}}$, a menos que${\displaystyle {\textsf {P}}={\textsf {NP}}}$. Un ejemplo clásico de un${\displaystyle {\textsf {para-NP}}}$El problema parametrizado -difícil es la coloración de grafos , parametrizada por el número k de colores, que ya está${\displaystyle {\textsf {NP}}}$-difícil para${\displaystyle k=3}$(véase Coloreado de grafos#Complejidad computacional ).

En general, existen dos maneras de definir una clase de complejidad: desde la teoría de máquinas y desde la lógica. En teoría de máquinas, una clase se define como el conjunto de problemas de decisión que puede resolver una clase de máquinas. En lógica, una clase se define como el conjunto de problemas de decisión que puede definirse mediante una clase de fórmulas lógicas.

Desde el punto de vista de la teoría de máquinas, un problema parametrizado pertenece a la clase W[w][d] si existe una reducción fpt del problema como la siguiente:

• Existen números enteros constantes${\displaystyle w,d}$, de tal manera que
• cada instancia${\displaystyle (x,k)}$se transforma en tiempo fpt en un circuito booleano que tiene una trama como máximo w y una profundidad como máximo d ,
• ${\displaystyle (x,k)\in L}$si y solo si el circuito tiene una asignación satisfactoria de peso k .

Aquí vemos que "W" significa "peso". Nótese que en la definición anterior,${\displaystyle w,d}$son independientes de${\displaystyle (x,k)}$, pero el circuito en sí depende de${\displaystyle (x,k)}$y puede cambiar si se modifica alguno de ellos${\displaystyle x}$o${\displaystyle k}$.

La clase W[w] se define entonces como su unión:$${\displaystyle W[w][1]\subset W[w][2]\subset \dots \subset W[w]:=\bigcup _{d\geq 1}W[w][d]}$$De forma más concisa, W[w] es el conjunto de problemas fpt-reducibles a una familia de circuitos booleanos específicos de instancia con weft${\displaystyle \leq w}$y una profundidad limitada por alguna constante específica del problema.

Un circuito normalizado de trama w y profundidad d es un circuito, donde el primero${\displaystyle d-w}$Las capas contienen solo pequeñas compuertas, y la última${\displaystyle w}$Las capas contienen grandes compuertas AND y OR alternadas. Se pueden iterar las leyes asociativas y las leyes de distribución de De Morgan para normalizar el circuito en tiempo fpt. Por lo tanto, sin pérdida de generalidad, podemos considerar solo circuitos normalizados. ^{[ 7 ]}

Desde el punto de vista de la teoría de modelos, la clase W[t] se define como la clase de problemas fpt-reducibles a${\displaystyle \operatorname {p-MC} (\Sigma _{t,1})}$.

Si bien la jerarquía W es una jerarquía contenida en NP, la jerarquía A imita más fielmente la jerarquía de tiempo polinomial de la complejidad clásica. Desde el punto de vista de la teoría de máquinas, la jerarquía A de problemas se define como problemas que son fpt-reducibles a computaciones mediante ciertos tipos de máquinas de Turing alternantes . La "A" significa "alternante". ^{[ 6 ]}

Desde el punto de vista de la teoría de modelos, la clase A[t] se define como la clase de problemas fpt-reducibles a${\displaystyle \operatorname {p-MC} (\Sigma _{t})}$.

Por ejemplo, el problema de la k -clique se puede especificar como un problema de verificación de modelos. El lenguaje tiene una única relación binaria.${\displaystyle E}$, dónde${\displaystyle E(x,y)}$medio "${\displaystyle x,y}$comparten una ventaja". Luego, un modelo finito${\displaystyle A}$es un grafo y tiene una k -clique si y solo si${\displaystyle A\models \phi _{k}}$, dónde$${\displaystyle \phi _{k}:=\exists x_{1:k},\bigwedge _{1\leq i<j\leq n}E(x_{i},x_{j})}$$Esto demuestra que el problema de la k -clique está en${\displaystyle A[1]}$.

Un problema es A[i] -completo si es A[i] y cualquier problema A[i] se reduce a él mediante fpt.

Por definición,$${\displaystyle W[0]\subset W[1]\subset \cdots ,\quad W[i]\subset A[i],\quad A[0]\subset A[1]\subset \cdots }$$${\displaystyle {\mathsf {FPT}}=W[0]=A[0]}$:

• ${\displaystyle W[0]=A[0]}$desde${\displaystyle \Sigma _{0}}$no tiene cuantificadores en absoluto, por lo que no hay diferencia entre${\displaystyle \Sigma _{0}}$y${\displaystyle \Sigma _{0,1}}$.
• ${\displaystyle {\mathsf {FPT}}\subset W[0]}$Para cualquier problema de FPT${\displaystyle L}$puede reducirse trivialmente a fpt de la siguiente manera: Resuelva el problema${\displaystyle (x,k)\in L}$en tiempo fpt, ​​luego genera un circuito trivial de Sí/No que no hace nada excepto generar el valor booleano correcto.
• ${\displaystyle {\mathsf {FPT}}\supset W[0]}$. Para cualquier problema W[0]${\displaystyle L}$y cualquier instancia de problema${\displaystyle c\in L}$, el circuito${\displaystyle c}$tiene 0 trama y${\displaystyle \leq d}$profundidad, donde${\displaystyle d}$es fijo. Por lo tanto, la salida está determinada por hasta${\displaystyle 2^{d}}$entradas. Todas las demás entradas son de libre uso. Por lo tanto, uno simplemente calcula por fuerza bruta todas${\displaystyle 2^{2^{d}}}$posibles entradas. Si una determinada entrada tiene un peso k' y hace que la salida del circuito sea verdadera, entonces compruebe si todavía hay suficientes entradas para completar el peso:${\displaystyle \#({\text{inputs of }}c)-2^{d}\geq k-k'}$.

${\displaystyle W[1]=A[1]}$. ^{[ 6 ]}

Intuitivamente, los problemas de la clase W[1] pueden interpretarse de la forma: ¿Existe un objeto de tamaño k con una determinada propiedad verificable localmente? En fórmula, sería de la forma$${\displaystyle \bigvee _{u_{1},\dots ,u_{k}}({\text{object constructed according to }}u_{1},\dots ,u_{k}{\text{ has a certain local property}})}$$De hecho, W[1] se reduce a W[1, 2] , la clase de problemas fpt-reducibles a circuitos booleanos de la forma${\displaystyle \bigwedge _{i}(x_{i,1}\lor x_{i,2})}$. Es decir, un gran AND sobre muchos OR de fan-in 2. ^{[ 8 ]}

Ejemplos de problemas W[1] -completos incluyen: ^{[ 8 ]}

• Conjunto independiente
  • Entrada: un gráfico G
  • Parámetro: un número entero k
  • Salida: Indica si G contiene un conjunto independiente de tamaño k.
• Camarilla
  • Entrada: un gráfico G
  • Parámetro: un número entero k
  • Salida: Si G contiene una camarilla de tamaño k
• No bloqueador bipartito
  • Entrada: un grafo bipartito${\displaystyle (V_{1},V_{2},E)}$
  • Parámetro: un número entero k
  • Salida: Si existe un subconjunto${\displaystyle S\subset V_{1}}$de tamaño k , de tal manera que cualquier${\displaystyle v\in V_{2}}$tiene un vecino${\displaystyle u\not \in S}$. En otras palabras,${\displaystyle S}$no bloquea${\displaystyle V_{2}}$.
• Peso- k 2-satisfacibilidad
  • Entrada: una fórmula normal conjuntiva de forma${\displaystyle \bigwedge _{i}(p_{i,1}\lor p_{i,2})}$, donde i abarca cláusulas .
  • Parámetro: un número entero k
  • Salida: Si existe una asignación de peso k que satisfaga la fórmula.
• Problema de la máquina de Turing corta.
  • Entrada: máquina de Turing no determinista M , una cadena x , un entero k .
  • Salida: Si existe una ruta computacional con la que M acepta x en como máximo k pasos.

Nótese que el problema simple sin bloqueo es FPT. ^{[ 9 ]}

Nota sobre la máquina de Turing no determinista. La máquina puede especificarse mediante cualquiera de las formulaciones estándar. Normalmente se considera la máquina de Turing de una cinta, pero el problema de la máquina de Turing corta sigue siendo W[1] incluso si permitimos f ( k ) cintas e incluso f ( k ) de cintas f ( k )-dimensionales, pero incluso con esta extensión, la restricción al tamaño del alfabeto de la cinta f ( k ) es FPT. Fundamentalmente, debido a que la máquina M misma es parte de la entrada del problema, el tamaño de entrada n es mayor que el número de estados de M. De esta manera, la máquina de Turing puede tomar una de${\displaystyle n}$posibles rutas de cálculo por paso, acceso${\displaystyle n^{O(k)}}$pasos en total dentro del tiempo k . Por lo tanto, vemos que W[1] no está obviamente contenido dentro de FPT .

El problema del conjunto independiente se puede codificar de esta manera. Dado cada grafo${\displaystyle (V,E)}$, su problema de conjunto independiente está codificado por el siguiente circuito booleano de trama 1:$${\displaystyle \Phi _{\text{IS}}(V,E):=\bigwedge _{\{u,v\}\in E}(\neg x_{u}\lor \neg x_{v})}$$dónde${\displaystyle E}$es el conjunto de aristas en el grafo. El grafo tiene un conjunto independiente de tamaño k si y solo si hay una entrada de peso k a su circuito booleano, tal que produce una salida de 1.

El problema de la camarilla se puede codificar como$${\displaystyle \Phi _{\text{clique}}(V,E):=\bigwedge _{\{u,v\}\subset V,u\neq v,\{u,v\}\not \in E}(\neg x_{u}\lor \neg x_{v})}$$Comprueba que no se puede elegir ningún par de vértices que no formen una arista, por lo que cualquier conjunto de vértices elegido se ve obligado a ser una camarilla.

El problema de la máquina de Turing corta se puede convertir en una fórmula booleana utilizando la misma idea de demostración que el teorema de Cook-Levin , que muestra que SAT es NP-completo codificando trazas computacionales de la máquina de Turing como fórmulas booleanas. La siguiente demostración proviene de ^{[ 8 ] [ 10 ]} . Específicamente, definamos las variables proposicionales:

• ${\displaystyle s_{t,i,j,a,b}}$: en el instante t , la máquina de Turing se encuentra en el estado i y transita al estado j , leyendo a y escribiendo b .
• ${\displaystyle y_{t,p,a,b}}$: en el instante t , la posición de la cinta p tiene el símbolo a , y en el instante (t+1) tiene el símbolo b .

De los índices, el tiempo t y la posición de la cinta p varían en 1:k . Los rangos de los índices para el estado de la máquina de Turing i, j , la transición m y los símbolos a, b están determinados por la descripción de la máquina M, pero ambos están acotados dentro de 1:n .

Luego, la fórmula${\displaystyle \Phi _{{\text{STM}},k}(M,x)}$es una conjunción de cláusulas que imponen las siguientes restricciones:

• No todas las transiciones de estado de una máquina de Turing están prohibidas por la regla de transición no determinista. Estas se ven como:${\displaystyle s_{t,i,j,a,b}\to \neg s_{t+1,i',j',a',b'}}$, en otras palabras,${\displaystyle \neg s_{t,i,j,a,b}\lor \neg s_{t+1,i',j',a',b'}}$. Hay${\displaystyle O(kn^{4})}$tales cláusulas.
• La máquina de Turing no puede estar en dos posiciones a la vez, ni puede realizar dos transiciones a la vez.
• La regla de transición no determinista no prohíbe ninguna transición de estado de las celdas de la cinta.
• Cada estado de celda de cinta no puede tener dos símbolos a la vez.
• En el instante 0, la máquina de Turing no ha salido de su estado y posición iniciales, y x no se ha borrado de la cinta.
• La máquina de Turing no se encuentra en un estado de rechazo en el instante k .

Luego, se especifica completamente un trazado computacional a través de la máquina de Turing estableciendo k variables de${\displaystyle s_{t,i,j,a,b}}$a Verdadero para indicar las transiciones de estado de la máquina de Turing en cada momento, y configurar${\displaystyle k^{2}}$variables de${\displaystyle y_{t,p,a,b}}$a Verdadero para indicar la transición del estado de la cinta en cada momento. Esto reduce el problema de la máquina de Turing corta a un problema de encontrar un peso-${\displaystyle (k+k^{2})}$asignación satisfactoria a un circuito booleano antimonótono de trama 1 y profundidad 2.

Los problemas W[2] son ​​intuitivamente de la forma: adivinar un objeto de tamaño k , realizar algún procesamiento local en el objeto y luego realizar un procesamiento global.

Ejemplos de problemas W [2]-completos incluyen:

• decidir si un grafo dado contiene un conjunto dominante de tamaño k.
• decidir si una máquina de Turing multitape no determinista dada acepta en k pasos (problema de aceptación de máquina de Turing multitape 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 W [2]-completa alternativa permite solo máquinas de Turing de una sola cinta, pero el tamaño del alfabeto puede depender de n .

El problema del conjunto dominante tiene fórmula${\displaystyle \Psi _{\text{dom}}(V,E)=\bigwedge _{u\in V}\bigvee _{v\in \operatorname {Neighbor} [u]}x_{v}}$.

Se sabe que algunos problemas son W[i] -completos, aunque tienen una forma computacionalmente genérica y suelen estudiarse dentro de la propia teoría de la complejidad parametrizada. Empíricamente, hasta 2013, casi todos los problemas parametrizados que surgieron de forma natural y que habían estudiado resultaron ser W[0] -completos, W[1] -completos o W[2] -completos. Los siguientes se utilizan habitualmente: ^{[ 4 ]}

• Satisfacibilidad ponderada i -normalizada: ^{[ 7 ] [ 4 ] : Teorema 23.2.1} Dada una fórmula booleana, escrita como un AND de OR de AND de ... de variables posiblemente negadas, con${\displaystyle i+1}$¿Es posible satisfacer capas alternas de AND u OR estableciendo exactamente k variables a 1?
  • Bosquejo de la prueba: Cualquier circuito W[i] puede normalizarse en tiempo fpt iterando la ley de asociación y la ley distributiva de De Morgan, demostrando así que este problema es W[i] -completo.
• Si i>0 es par, entonces
  • ${\displaystyle {\text{monotone-}}W[i]=W[i]}$.
  • La satisfacibilidad monótona ponderada i -normalizada es W[i] -completa.
  • La satisfacibilidad normalizada monótona ponderada (i+1) está en W[i] .
• Si i>0 es impar, entonces
  • ${\displaystyle {\text{antimonotone-}}W[i]=W[i]}$
  • La satisfacibilidad normalizada i - antionotona ponderada es W[i] -completa.
  • Si${\displaystyle i\geq 3}$, entonces la Satisfacibilidad Normalizada Antimonótona Ponderada (i+1) está en W[i] .

Estos problemas son esencialmente "artificiales", ya que no se estudian excepto dentro del contexto de la complejidad parametrizada. La literatura reporta pocos problemas que ocurren naturalmente que sean W[i] -completos para${\displaystyle i\geq 3}$:

• La detección de dependencias de inclusión en bases de datos relacionales es W[3] -completa.
• Ciertos problemas en los modelos de cadena de suministro son W[3] -completos o W[4] -completos. ^{[ 11 ]}

La jerarquía W* es similar a la jerarquía W , pero parametriza la profundidad en lugar de mantenerla constante. La clase W*[t] se define como la clase de problemas fpt-reducibles a este problema: ^{[ 5 ]}

• Entrada: un circuito booleano de trama de como máximo t y profundidad de como máximo k ,
• Parámetro: k
• Salida: Si el circuito booleano tiene una asignación que satisface el peso k .

Está relacionado con W por: ^{[ 4 ]}$${\displaystyle W^{*}[1]=W[1],\;W^{*}[2]=W[2],\;W[t]\subset W^{*}[t]\subset W[t+2],\quad \forall t\geq 1}$$La jerarquía AW se obtiene añadiendo alternancia a la jerarquía W. La clase AW[t] se define como la clase de problemas fpt-reducibles a este problema: ^{[ 5 ] [ 6 ]}

• Entrada: un circuito booleano de trama de a lo sumo t , y una partición de sus entradas a${\displaystyle I_{1}\cup I_{2}\cup \cdots \cup I_{r}}$
• Parámetro:${\displaystyle (r,k_{1},\dots ,k_{r})}$
• Salida: Si el circuito booleano es satisfacible bajo pesos alternos.${\displaystyle (k_{1},\dots ,k_{r})}$condiciones.

El peso alterno-${\displaystyle (k_{1},\dots ,k_{r})}$se define de la siguiente manera:

• Existe un subconjunto${\displaystyle J_{1}\subset I_{1}}$de tamaño${\displaystyle k_{1}}$, de tal manera que si establecemos exactamente esas entradas en Verdadero y las demás en Falso, entonces,
• para cualquier subconjunto${\displaystyle J_{2}\subset I_{2}}$de tamaño${\displaystyle k_{2}}$, de tal manera que si establecemos exactamente esas entradas en Verdadero y las demás en Falso, entonces,
• ...
• El circuito booleano devuelve Verdadero.

Esto puede interpretarse como un juego de dos jugadores, donde el primer jugador intenta que la salida del circuito sea verdadera y el segundo jugador intenta que la salida del circuito sea falsa. El primer jugador realiza un movimiento estableciendo exactamente${\displaystyle k_{1}}$entradas de${\displaystyle I_{1}}$a Verdadero y los demás a Falso, luego el segundo jugador hace un movimiento en${\displaystyle I_{2}}$, etc. El circuito está bajo carga alterna.${\displaystyle (k_{1},\dots ,k_{r})}$condiciones si y solo si el jugador 1 tiene una estrategia ganadora.

Resulta que la jerarquía se derrumba:${\displaystyle AW[1]=AW[2]=\cdots }$Así, la literatura simplemente escribe un símbolo común para ellos:${\displaystyle AW[\ast ]:=AW[1]=AW[2]=\cdots }$.

• Downey, Rod G.; Fellows , Michael R. (1999). Complejidad parametrizada . Springer. doi : 10.1007/978-1-4612-0515-9 . ISBN 978-0-387-94883-6.
• Niedermeier, Rolf (2006). Invitación a algoritmos de parámetros fijos . Prensa de la Universidad de Oxford. ISBN 978-0-19-856607-6.Un libro de texto introductorio.
• Flum, Jörg ; Grohe, Martin (2006). Teoría de la complejidad parametrizada . Springer. doi : 10.1007/3-540-29953-X . ISBN 978-3-540-29952-3.Una introducción actualizada al libro de texto de 1999.
• Downey, Rodney G.; Fellows, Michael R. (2013). Fundamentos de la complejidad parametrizada . Textos en informática. Londres: Springer London. doi : 10.1007/978-1-4471-5559-1 . ISBN 978-1-4471-5558-4.Un libro de texto no introductorio escrito para describir los avances posteriores al libro de texto de 1999.
• Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Algoritmos parametrizados . Saltador. ISBN 978-3-319-21274-6.