PLS (complejidad)

Clase de complejidad

En la teoría de la complejidad computacional , la búsqueda local polinómica ( PLS ) es una clase de complejidad que modela la dificultad de encontrar una solución localmente óptima para un problema de optimización . Las características principales son:

Los problemas que presenta PLS son que el costo de una solución se puede calcular en tiempo polinómico y que la vecindad de una solución se puede buscar en tiempo polinómico. Por lo tanto, es posible verificar si una solución es o no un óptimo local en tiempo polinómico.

Además, dependiendo del problema y del algoritmo que se utilice para resolverlo, podría ser más rápido encontrar un óptimo local en lugar de un óptimo global.

Descripción

Al buscar un óptimo local, hay dos cuestiones interesantes que abordar: primero, cómo encontrar un óptimo local y segundo, cuánto tiempo se tarda en encontrarlo. En el caso de muchos algoritmos de búsqueda local, no se sabe si pueden encontrar un óptimo local en tiempo polinomial o no. ^[1] Por lo tanto, para responder a la pregunta de cuánto tiempo se tarda en encontrar un óptimo local, Johnson, Papadimitriou y Yannakakis ^[2] introdujeron la clase de complejidad PLS en su artículo "¿Qué tan fácil es la búsqueda local?". Contiene problemas de búsqueda local para los cuales la optimalidad local se puede verificar en tiempo polinomial.

Un problema de búsqueda local está en PLS, si se cumplen las siguientes propiedades:

• El tamaño de cada solución está limitado polinomialmente por el tamaño de la instancia . ${\displaystyle I}$
• Es posible encontrar alguna solución de una instancia del problema en tiempo polinomial.
• Es posible calcular el coste de cada solución en tiempo polinomial.
• Es posible encontrar todos los vecinos de cada solución en tiempo polinomial.

Con estas propiedades es posible encontrar para cada solución la mejor solución vecina o si no existe tal mejor solución vecina, afirmar que es un óptimo local. ${\displaystyle s}$ ${\displaystyle s}$

Ejemplo

Consideremos el siguiente ejemplo del problema Max-2Sat : . El objetivo es encontrar una asignación que maximice la suma de las cláusulas satisfechas. ${\displaystyle I}$ ${\displaystyle (x_{1}\vee x_{2})\wedge (\neg x_{1}\vee x_{3})\wedge (\neg x_{2}\vee x_{3})}$

Una solución para esa instancia es una cadena de bits que asigna a cada uno el valor 0 o 1. En este caso, una solución consta de 3 bits, por ejemplo , que representa la asignación de a con el valor 0. El conjunto de soluciones es el conjunto de todas las asignaciones posibles de , y . ${\displaystyle s}$ ${\displaystyle x_{i}}$ ${\displaystyle s=000}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{3}}$ ${\displaystyle F_{L}(I)}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$

El costo de cada solución es el número de cláusulas satisfechas, porque la segunda y la tercera cláusula se satisfacen. ${\displaystyle c_{L}(I,s=000)=2}$

El vecino Flip de una solución se alcanza invirtiendo un bit de la cadena de bits , por lo que los vecinos de tienen los siguientes costos: ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle N(I,000)=\{100,010,001\}}$

${\displaystyle c_{L}(I,100)=2}$

${\displaystyle c_{L}(I,010)=2}$

${\displaystyle c_{L}(I,001)=2}$

No existen vecinos con mejores costes que , si buscamos una solución con coste máximo. Aunque no es un óptimo global (que por ejemplo sería una solución que satisface todas las cláusulas y tiene ), es un óptimo local, porque ninguno de sus vecinos tiene mejores costes. ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s'=111}$ ${\displaystyle c_{L}(I,s')=3}$ ${\displaystyle s}$

Intuitivamente se puede argumentar que este problema radica en PLS , porque:

• Es posible encontrar una solución a una instancia en tiempo polinomial, por ejemplo, estableciendo todos los bits en 0.
• Es posible calcular el costo de una solución en tiempo polinomial, recorriendo una vez toda la instancia y contando las cláusulas que se satisfacen.
• Es posible encontrar todos los vecinos de una solución en tiempo polinomial, tomando el conjunto de soluciones que difieren en exactamente un bit. ${\displaystyle s}$

Si simplemente contamos la cantidad de cláusulas satisfechas, el problema se puede resolver en tiempo polinómico, ya que la cantidad de costos posibles es polinómica. Sin embargo, si asignamos a cada cláusula un peso entero positivo (y buscamos maximizar localmente la suma de pesos de las cláusulas satisfechas), el problema se vuelve PLS-completo (abajo).

Definición formal

Un problema de búsqueda local tiene un conjunto de instancias que se codifican utilizando cadenas sobre un alfabeto finito . Para cada instancia existe un conjunto de soluciones finito . Sea la relación que modela . La relación está en PLS ^{[2] [3] [4]} si: ${\displaystyle L}$ ${\displaystyle D_{L}}$ ${\displaystyle \Sigma }$ ${\displaystyle I}$ ${\displaystyle F_{L}(I)}$ ${\displaystyle R}$ ${\displaystyle L}$ ${\displaystyle R\subseteq D_{L}\times F_{L}(I):=\{(I,s)\mid I\in D_{L},s\in F_{L}(I)\}}$

• El tamaño de cada solución está limitado polinómicamente en el tamaño de ${\displaystyle s\in F_{L}(I)}$ ${\displaystyle I}$
• Las instancias y soluciones de los problemas son verificables en tiempo polinomial. ${\displaystyle I\in D_{L}}$ ${\displaystyle s\in F_{L}(I)}$
• Hay una función computable en tiempo polinomial que devuelve para cada instancia alguna solución. ${\displaystyle A:D_{L}\rightarrow F_{L}(I)}$ ${\displaystyle I\in D_{L}}$ ${\displaystyle s\in F_{L}(I)}$
• Hay una función computable en tiempo polinomial ^[5] que devuelve para cada solución de una instancia el costo ${\displaystyle B:D_{L}\times F_{L}(I)\rightarrow \mathbb {R} ^{+}}$ ${\displaystyle s\in F_{L}(I)}$ ${\displaystyle I\in D_{L}}$ ${\displaystyle c_{L}(I,s)}$
• Hay una función computable en tiempo polinomial que devuelve el conjunto de vecinos para un par instancia-solución ${\displaystyle N:D_{L}\times F_{L}(I)\rightarrow Powerset(F_{L}(I))}$
• Hay una función computable en tiempo polinomial que devuelve una solución vecina con un mejor costo que la solución , o indica que es localmente óptima ${\displaystyle C:D_{L}\times F_{L}(I)\rightarrow N(I,s)\cup \{OPT\}}$ ${\displaystyle s'}$ ${\displaystyle s}$ ${\displaystyle s}$
• Para cada instancia , contiene exactamente los pares donde es una solución óptima local de ${\displaystyle I\in D_{L}}$ ${\displaystyle R}$ ${\displaystyle (I,s)}$ ${\displaystyle s}$ ${\displaystyle I}$

Una instancia tiene la estructura de un gráfico implícito (también llamado gráfico de transición ^[6] ), cuyos vértices son las soluciones con dos soluciones conectadas por un arco dirigido si y solo si . ${\displaystyle D_{L}}$ ${\displaystyle s,s'\in F_{L}(I)}$ ${\displaystyle s'\in N(I,s)}$

Un óptimo local es una solución que no tiene un vecino con mejores costos. En el gráfico implícito, un óptimo local es un sumidero. Un vecindario donde cada óptimo local es un óptimo global , que es una solución con el mejor costo posible, se llama vecindario exacto . ^{[6] [1]} ${\displaystyle s}$

Definición alternativa

La clase PLS es la clase que contiene todos los problemas que se pueden reducir en tiempo polinomial al problema Sink-of- DAG ^[7] (también llamado Local-Opt ^[8] ): Dados dos enteros y y dos circuitos booleanos tales que y , encuentre un vértice tal que y o . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle S:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$ ${\displaystyle S(0^{n})\neq 0^{n}}$ ${\displaystyle V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle S(x)\neq x}$ ${\displaystyle S(S(x))=S(x)}$ ${\displaystyle V(S(x))\leq V(x)}$

Ejemplos de estructuras de barrio

Ejemplos de estructuras de vecindad para problemas con variables booleanas (o cadenas de bits) como solución:

• Inversión ^[2] - La vecindad de una solución se puede lograr negando (invirtiendo) un bit de entrada arbitrario . Por lo tanto, una solución y todos sus vecinos tienen una distancia de Hamming de uno: . ${\displaystyle s=x_{1},...,x_{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle s}$ ${\displaystyle r\in N(I,s)}$ ${\displaystyle H(s,r)=1}$
• Kernighan-Lin ^{[2] [6]} - Una solución es vecina de solución si se puede obtener de mediante una secuencia de volteretas voraces, donde ningún bit se voltea dos veces. Esto significa que, comenzando con , el Flip -vecino de con el mejor costo, o la menor pérdida de costo, se elige para ser vecino de s en la estructura de Kernighan-Lin. Así como el mejor (o menos peor) vecino de , y así sucesivamente, hasta que es una solución donde cada bit de se niega. Tenga en cuenta que no está permitido voltear un bit hacia atrás, si una vez se ha volteado. ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s_{1}}$ ${\displaystyle s}$ ${\displaystyle s_{1}}$ ${\displaystyle s_{i}}$ ${\displaystyle s}$
• k-Flip ^[9] - Una solución es vecina de una solución si la distancia de Hamming entre y es como máximo , por lo que . ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle H}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle k}$ ${\displaystyle H(s,r)\leq k}$

Ejemplos de estructuras de vecindad para problemas en gráficos:

• Intercambio ^[10] - Una partición de nodos en un gráfico es vecina de una partición si se puede obtener intercambiando un nodo con un nodo . ${\displaystyle (P_{2},P_{3})}$ ${\displaystyle (P_{0},P_{1})}$ ${\displaystyle (P_{2},P_{3})}$ ${\displaystyle (P_{0},P_{1})}$ ${\displaystyle p_{0}\in P_{0}}$ ${\displaystyle p_{1}\in P_{1}}$
• Kernighan-Lin ^{[1] [2]} - Una partición es un vecino de si se puede obtener mediante una secuencia voraz de intercambios de nodos en con nodos en . Esto significa que los dos nodos y se intercambian, donde la partición gana el mayor peso posible o pierde el menor peso posible. Tenga en cuenta que no se permite intercambiar ningún nodo dos veces. Esta regla se basa en la heurística de Kernighan-Lin para la partición de grafos . ${\displaystyle (P_{2},P_{3})}$ ${\displaystyle (P_{0},P_{1})}$ ${\displaystyle (P_{2},P_{3})}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{1}}$ ${\displaystyle p_{0}\in P_{0}}$ ${\displaystyle p_{1}\in P_{1}}$ ${\displaystyle ((P_{0}\setminus p_{0})\cup p1,(P_{1}\setminus p_{1})\cup p_{0})}$
• Fiduccia-Matheyses ^{[1] [11]} - Este vecindario es similar a la estructura de vecindario de Kernighan-Lin, es una secuencia voraz de intercambios, excepto que cada intercambio ocurre en dos pasos. Primero, el nodo con la mayor ganancia de costo, o la menor pérdida de costo, se intercambia con , luego, el nodo con el mayor costo, o la menor pérdida de costo, se intercambia con para equilibrar las particiones nuevamente. Los experimentos han demostrado que Fiduccia-Matheyses tiene un tiempo de ejecución menor en cada iteración del algoritmo estándar, aunque a veces encuentra un óptimo local inferior. ${\displaystyle p_{0}\in P_{0}}$ ${\displaystyle P_{1}}$ ${\displaystyle p_{1}\in P_{1}}$ ${\displaystyle P_{0}}$
• FM-Swap ^[1] - Esta estructura de vecindad se basa en la estructura de vecindad de Fiduccia-Mattheyses. Cada solución tiene solo un vecino, la partición obtenida después del primer intercambio de Fiduccia-Mattheyses. ${\displaystyle s=(P_{0},P_{1})}$

El algoritmo estándar

Considere el siguiente problema computacional: dada alguna instancia de un problema PLS , encuentre una solución localmente óptima tal que para todo ${\displaystyle I}$ ${\displaystyle L}$ ${\displaystyle s\in F_{L}(I)}$ ${\displaystyle c_{L}(I,s')\geq c_{L}(I,s)}$ ${\displaystyle s'\in N(I,s)}$ .

Cada problema de búsqueda local se puede resolver utilizando el siguiente algoritmo de mejora iterativa: ^[2]

1. Úselo para encontrar una solución inicial ${\displaystyle A_{L}}$ ${\displaystyle s}$
2. Utilice el algoritmo para encontrar una mejor solución . Si existe dicha solución, reemplácela por y repita el paso 2; de lo contrario, vuelva. ${\displaystyle C_{L}}$ ${\displaystyle s'\in N(I,s)}$ ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle s}$

Desafortunadamente, generalmente se necesita una cantidad exponencial de pasos de mejora para encontrar un óptimo local, incluso si el problema se puede resolver exactamente en tiempo polinomial. ^[2] No siempre es necesario utilizar el algoritmo estándar, puede haber un algoritmo diferente y más rápido para un problema determinado. Por ejemplo, un algoritmo de búsqueda local utilizado para la programación lineal es el algoritmo Simplex . ${\displaystyle L}$

El tiempo de ejecución del algoritmo estándar es pseudopolinomial en el número de costos diferentes de una solución. ^[12]

El espacio que necesita el algoritmo estándar es solo polinómico. Solo necesita guardar la solución actual , que está acotada por definición. ^[1] ${\displaystyle s}$

Reducciones

Se puede utilizar una reducción de un problema a otro para demostrar que el segundo problema es al menos tan difícil como el primero. En particular, se utiliza una reducción PLS para demostrar que un problema de búsqueda local que se encuentra en PLS también es PLS-completo, reduciendo un problema PLS-completo a uno que se demostrará que es PLS-completo.

Reducción de PLS

Un problema de búsqueda local es reducible mediante PLS ^[2] a un problema de búsqueda local si hay dos funciones de tiempo polinomiales y tales que: ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle f:D_{1}\rightarrow D_{2}}$ ${\displaystyle g:D_{1}\times F_{2}(f(I_{1}))\rightarrow F_{1}(I_{1})}$

• Si es una instancia de , entonces es una instancia de ${\displaystyle I_{1}}$ ${\displaystyle L_{1}}$ ${\displaystyle f(I_{1})}$ ${\displaystyle L_{2}}$
• Si es una solución para de , entonces es una solución para de ${\displaystyle s_{2}}$ ${\displaystyle f(I_{1})}$ ${\displaystyle L_{2}}$ ${\displaystyle g(I_{1},s_{2})}$ ${\displaystyle I_{1}}$ ${\displaystyle L_{1}}$
• Si es un óptimo local por ejemplo de , entonces tiene que ser un óptimo local por ejemplo de ${\displaystyle s_{2}}$ ${\displaystyle f(I_{1})}$ ${\displaystyle L_{2}}$ ${\displaystyle g(I_{1},s_{2})}$ ${\displaystyle I_{1}}$ ${\displaystyle L_{1}}$

Es suficiente mapear únicamente los óptimos locales de a los óptimos locales de , y mapear todas las demás soluciones, por ejemplo, a la solución estándar devuelta por . ^[6] ${\displaystyle f(I_{1})}$ ${\displaystyle I_{1}}$ ${\displaystyle A_{1}}$

Las reducciones PLS son transitivas . ^[2]

Reducción estricta de PLS

Definición Gráfico de transición

El gráfico de transición ^[6] de una instancia de un problema es un gráfico dirigido. Los nodos representan todos los elementos del conjunto finito de soluciones y las aristas apuntan desde una solución hasta la vecina con un costo estrictamente mejor. Por lo tanto, es un gráfico acíclico. Un sumidero, que es un nodo sin aristas salientes, es un óptimo local. La altura de un vértice es la longitud del camino más corto desde el sumidero más cercano. La altura del gráfico de transición es la mayor de las alturas de todos los vértices, por lo que es la altura del camino más corto posible desde un nodo hasta su sumidero más cercano. ${\displaystyle T_{I}}$ ${\displaystyle I}$ ${\displaystyle L}$ ${\displaystyle F_{L}(I)}$ ${\displaystyle v}$ ${\displaystyle v}$

Definición Reducción PLS estricta

Una reducción PLS de un problema de búsqueda local a un problema de búsqueda local es una reducción PLS estricta ^[10] si para cualquier instancia de , se puede elegir un subconjunto de soluciones de la instancia de , de modo que se satisfagan las siguientes propiedades: ${\displaystyle (f,g)}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle I_{1}}$ ${\displaystyle L_{1}}$ ${\displaystyle R}$ ${\displaystyle I_{2}=f(I_{1})}$ ${\displaystyle L_{2}}$

• ${\displaystyle R}$contiene, entre otras soluciones, todos los óptimos locales de ${\displaystyle I_{2}}$
• Para cada solución de , se puede construir una solución de en tiempo polinomial, de modo que ${\displaystyle p}$ ${\displaystyle I_{1}}$ ${\displaystyle q\in R}$ ${\displaystyle I_{2}=f(I_{1})}$ ${\displaystyle g(I_{1},q)=p}$
• Si el gráfico de transición de contiene una ruta directa desde a , y , pero todos los vértices de la ruta interna están fuera de , entonces para las soluciones correspondientes y se cumple o contiene una arista desde a ${\displaystyle T_{f(I_{1})}}$ ${\displaystyle f(I_{1})}$ ${\displaystyle q}$ ${\displaystyle q_{0}}$ ${\displaystyle q,q_{0}\in R}$ ${\displaystyle R}$ ${\displaystyle p=g(I_{1},q)}$ ${\displaystyle p_{0}=g(I_{1},q_{0})}$ ${\displaystyle p=p_{0}}$ ${\displaystyle T_{I_{1}}}$ ${\displaystyle p}$ ${\displaystyle p_{0}}$

Relación con otras clases de complejidad

PLS se encuentra entre las versiones funcionales de P y NP : FP ⊆ PLS ⊆ FNP . ^[2]

PLS también es una subclase de TFNP , ^[13] que describe problemas computacionales en los que se garantiza la existencia de una solución y se puede reconocer en tiempo polinomial. Para un problema en PLS, se garantiza la existencia de una solución porque el vértice de costo mínimo de todo el gráfico es una solución válida, y la validez de una solución se puede verificar calculando sus vecinos y comparando los costos de cada uno con el de otro.

También se demuestra que si un problema PLS es NP-hard , entonces NP = co-NP . ^[2]

PLS-completitud

Definición

Un problema de búsqueda local es PLS-completo, ^[2] si ${\displaystyle L}$

• ${\displaystyle L}$está en PLS
• Cada problema en PLS puede ser reducido a PLS ${\displaystyle L}$

Se ha demostrado que la versión de optimización del problema del circuito bajo la estructura de vecindad Flip es el primer problema PLS completo. ^[2]

Lista de problemas de PLS-complete

Esta es una lista incompleta de algunos problemas conocidos que son PLS-complete. Los problemas aquí son las versiones ponderadas; por ejemplo, Max-2SAT/Flip es ponderado aunque Max-2SAT normalmente se refiere a la versión no ponderada.

Descripción general de los problemas PLS-completos y cómo se reducen entre sí. Sintaxis: Optimización-Problema/Estructura de vecindad. Flecha punteada: Reducción PLS de un problema a otro . Flecha negra: Reducción PLS estricta. ^[4] ${\displaystyle L}$ ${\displaystyle Q:L\leftarrow Q}$

Notación: Problema / Estructura del vecindario

• Se ha demostrado que Min/Max-circuit/Flip es el primer problema PLS completo. ^[2]
• El sumidero de DAG es completo por definición.
• Se ha demostrado que Positive-not-all-equal-max-3Sat/Flip es PLS-completo mediante una reducción PLS estricta de Min/Max-circuit/Flip a Positive-not-all-equal-max-3Sat/Flip. Tenga en cuenta que Positive-not-all-equal-max-3Sat/Flip también se puede reducir a partir de Max-Cut/Flip. ^[10]
• Se ha demostrado que Positive-not-all-equal-max-3Sat/Kernighan-Lin es PLS-completo a través de una reducción PLS estricta de Min/Max-circuit/Flip a Positive-not-all-equal-max-3Sat/Kernighan-Lin. ^[1]
• Se ha demostrado que Max-2Sat /Flip es PLS-completo a través de una reducción PLS ajustada de Max-Cut/Flip a Max-2Sat/Flip. ^{[1] [10]}
• Se ha demostrado que Min-4Sat-B /Flip es PLS-completo a través de una reducción PLS estricta de Min-circuit/Flip a Min-4Sat-B/Flip. ^[9]
• Se ha demostrado que Max-4Sat-B/Flip (o CNF-SAT) es PLS-completo a través de una reducción PLS de Max-circuit/Flip a Max-4Sat-B/Flip. ^[14]
• Se ha demostrado que Max-4Sat-(B=3)/Flip es PLS-completo a través de una reducción PLS de Max-circuit/Flip a Max-4Sat-(B=3)/Flip. ^[15]
• Se ha demostrado que Max-Uniform-Graph-Partitioning /Swap es PLS-completo a través de una reducción PLS estricta de Max-Cut/Flip a Max-Uniform-Graph-partitioning/Swap. ^[10]
• Se afirma que Max-Uniform-Graph-Partitioning /Fiduccia-Matheyses es PLS-completo sin prueba. ^[1]
• Se ha demostrado que Max-Uniform-Graph-Partitioning /FM-Swap es PLS-completo a través de una reducción PLS estricta de Max-Cut/Flip a Max-Uniform-Graph-partitioning/FM-Swap. ^[10]
• Se ha demostrado que Max-Uniform-Graph-Partitioning /Kernighan-Lin es PLS-completo a través de una reducción PLS de Min/Max-circuit/Flip a Max-Uniform-Graph-Partitioning/Kernighan-Lin. ^[2] También hay una reducción PLS estricta de Positive-not-all-equal-max-3Sat/Kernighan-Lin a Max-Uniform-Graph-Partitioning/Kernighan-Lin. ^[1]
• Se ha demostrado que Max-Cut /Flip es PLS-completo a través de una reducción PLS estricta de Positive-not-all-equal-max-3Sat/Flip a Max-Cut/Flip. ^{[1] [10]}
• Se afirma que Max-Cut /Kernighan-Lin es PLS-completo sin pruebas. ^[6]
• Se ha demostrado que Min-Independent-Dominating-Set-B/k-Flip es PLS-completo a través de una reducción PLS estricta de Min-4Sat-B ′ /Flip a Min-Independent-Dominating-Set-B/k-Flip. ^[9]
• Se afirma que el conjunto independiente ponderado /cambio es PLS-completo sin prueba. ^{[2] [10] [6]}
• El subgrafo ponderado máximo con propiedad P/cambio es PLS-completo si la propiedad P = "no tiene aristas", ya que entonces es igual al conjunto independiente ponderado/cambio. También se ha demostrado que es PLS-completo para una propiedad P general hereditaria y no trivial mediante una reducción PLS estricta del conjunto independiente ponderado/cambio al subgrafo ponderado máximo con propiedad P/cambio. ^[16]
• Se ha demostrado que Set-Cover /k-change es PLS-completo para cada k ≥ 2 a través de una reducción PLS estricta de (3, 2, r)-Max-Constraint-Assignment/Change a Set-Cover/k-change. ^[17]
• Se ha demostrado que Metric-TSP /k-Change es PLS-completo a través de una reducción PLS de Max-4Sat-B/Flip a Metric-TSP/k-Change. ^[15]
• Se ha demostrado que Metric-TSP /Lin-Kernighan es PLS-completo a través de una reducción PLS estricta de Max-2Sat/Flip a Metric-TSP/Lin-Kernighan. ^[18]
• Se ha demostrado que la programación local multiprocesador /k-cambio es PLS-completa a través de una reducción PLS estricta de coincidencia tridimensional ponderada/(p, q)-intercambio a programación local multiprocesador/(2p+q)-cambio, donde (2p + q) ≥ 8. ^[5]
• Se ha demostrado que la Programación Multiprocesador Autoísta/k-cambio-con-propiedad-t es PLS-completa a través de una reducción PLS estricta de Emparejamiento tridimensional ponderado/(p, q)-Intercambio a (2p+q)-Programación Multiprocesador Autoísta/k-cambio-con-propiedad-t, donde (2p + q) ≥ 8. ^[5]
• Se ha demostrado que encontrar un equilibrio de Nash puro en un juego /cambio de congestión general es PLS-completo mediante una reducción PLS estricta de Positivo-no-todos-iguales-máximo-3Sat/Flip a Juego/cambio de congestión general. ^[19]
• Se ha demostrado que encontrar un equilibrio de Nash puro en un juego/cambio de congestión general simétrico es PLS-completo mediante una reducción PLS estricta de un juego/cambio de congestión general asimétrico a un juego/cambio de congestión general simétrico. ^[19]
• Se ha demostrado que encontrar un equilibrio de Nash puro en un juego/cambio de congestión de red dirigida asimétrico es PLS-completo a través de una reducción estricta de Positive-not-all-equal-max-3Sat/Flip a juegos/cambio de congestión de red dirigida ^[19] y también a través de una reducción PLS estricta de juegos/cambio de 2 umbrales a juegos/cambio de congestión de red dirigida ^{[20] .}
• Se ha demostrado que encontrar un equilibrio de Nash puro en un juego/cambio de congestión de red no dirigida asimétrica es PLS-completo a través de una reducción PLS estricta de juegos/cambio de 2 umbrales a juegos/cambio de congestión de red no dirigida asimétrica. ^[20]
• Se ha demostrado que encontrar un equilibrio de Nash puro en un juego de congestión de red simétrica delimitada por distancia es PLS-completo a través de una reducción PLS estricta de juegos de 2 umbrales a juegos de congestión de red simétrica delimitada por distancia. ^[21]
• Se ha demostrado que encontrar un equilibrio de Nash puro en un juego/cambio de 2 umbrales es PLS-completo mediante una reducción estricta de Max-Cut/Flip a un juego/cambio de 2 umbrales. ^[20]
• Se ha demostrado que encontrar un equilibrio de Nash puro en un juego/cambio de reparto de mercado con costos acotados por polinomios es PLS-completo a través de una reducción PLS estricta de juegos/cambio de 2 umbrales a un juego/cambio de reparto de mercado. ^[20]
• Se ha demostrado que la búsqueda de un equilibrio de Nash puro en un diseño/cambio de red superpuesta es PLS-completa mediante una reducción de juegos/cambio de 2 umbrales a diseño/cambio de red superpuesta. De manera análoga a la prueba del juego/cambio de congestión de red dirigida asimétrica, la reducción es estricta. ^[20]
• Se ha demostrado que la programación entera Min-0-1 /k-Flip es PLS-completa a través de una reducción PLS estricta de Min-4Sat-B ′ /Flip a la programación entera Min-0-1/k-Flip. ^[9]
• Se afirma que la Programación de Entero Máximo 0-1 /k-Flip es PLS-completa debido a la reducción PLS a Programación de Entero Máximo 0-1/k-Flip, pero se omite la prueba. ^[9]
• (p, q, r)-Asignación de restricción máxima
  • Se ha demostrado que (3, 2, 3)-Max-Constraint-Assignment-3-partite/Change es PLS-completo a través de una reducción PLS estricta de Circuit/Flip a (3, 2, 3)-Max-Constraint-Assignment-3-partite/Change. ^[22]
  • Se ha demostrado que (2, 3, 6)-Max-Constraint-Assignment-2-partite/Change es PLS-completo a través de una reducción PLS estricta de Circuit/Flip a (2, 3, 6)-Max-Constraint-Assignment-2-partite/Change. ^[22]
  • Se ha demostrado que (6, 2, 2)-Max-Constraint-Assignment/Change es PLS-completo a través de una reducción estricta de Circuit/Flip a (6,2, 2)-Max-Constraint-Assignment/Change. ^[22]
  • (4, 3, 3)-Max-Constraint-Assignment/Change es igual a Max-4Sat-(B=3)/Flip y se ha demostrado que es PLS-completo a través de una reducción PLS a partir de Max-circuit/Flip. ^[15] Se afirma que la reducción se puede extender de modo que se obtenga estrechez. ^[22]
• Se ha demostrado que Nearest-Colorful-Polytope/Change es PLS-completo a través de una reducción PLS de Max-2Sat/Flip a Nearest-Colorful-Polytope/Change. ^[3]
• Se ha demostrado que la configuración estable/inversión en una red de Hopfield es PLS completa si los umbrales son 0 y los pesos son negativos mediante una reducción PLS estricta de Max-Cut/Flip a configuración estable/inversión. ^{[1] [10] [18]}
• Se ha demostrado que el intercambio de correspondencia tridimensional ponderado /(p, q) es PLS-completo para p ≥9 y q ≥ 15 a través de una reducción PLS estricta de (2, 3, r)-Asignación de restricción máxima-2-partita/Cambio a intercambio de correspondencia tridimensional ponderado/(p, q) ^{[5] .}
• El problema Real-Local-Opt (encontrar el óptimo local ɛ de una función objetivo continua λ-Lipschitz y una función de vecindad ) es PLS-completo. ^[8] ${\displaystyle V:[0,1]^{3}\rightarrow [0,1]}$ ${\displaystyle S:[0,1]^{3}\rightarrow [0,1]^{3}}$
• Se demostró que encontrar un pico de aptitud local en un paisaje de aptitud biológica especificado por el modelo NK /mutación puntual con K ≥ 2 era PLS-completo a través de una reducción PLS ajustada de Max-2SAT/Flip. ^[23]

Relaciones con otras clases de complejidad

Fearnley, Goldberg, Hollender y Savani ^[24] demostraron que una clase de complejidad llamada CLS es igual a la intersección de PPAD y PLS.

Lectura adicional

• Equilibrios, puntos fijos y clases de complejidad: un estudio. ^[25]

Referencias

• Yannakakis, Mihalis (2009), "Equilibrios, puntos fijos y clases de complejidad", Computer Science Review , 3 (2): 71–85, CiteSeerX  10.1.1.371.5034 , doi :10.1016/j.cosrev.2009.03.004.

1. Yannakakis, Mihalis (2003). Búsqueda local en optimización combinatoria - Complejidad computacional . Princeton University Press. págs. 19–55. ISBN 9780691115221.
2. Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "¿Qué tan fácil es la búsqueda local?". Journal of Computer and System Sciences . 37 (1): 79–100. doi : 10.1016/0022-0000(88)90046-3 .
3. Mulzer, Wolfgang; Stein, Yannik (14 de marzo de 2018). "Aspectos computacionales del teorema colorido de Caratheodory". Geometría discreta y computacional . 60 (3): 720–755. arXiv : 1412.3347 . Código Bibliográfico :2014arXiv1412.3347M. doi :10.1007/s00454-018-9979-y. S2CID  254024141.
4. Borzechowski, Michaela. "La clase de complejidad Búsqueda local polinómica (PLS) y problemas PLS-completos" (PDF) .
5. Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009). "La programación multiprocesador es PLS completa". Ciencias de Sistemas, 2009. HICSS'09. 42ª Conferencia Internacional de Hawái el : 1–10.
6. , Wil; Aarts, Emilio; Korst, enero (2010). Aspectos teóricos de la búsqueda local . Medios de ciencia y negocios de Springer. ISBN 9783642071485.
7. Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul (diciembre de 2020). "Final único de línea potencial". Revista de Ciencias de la Computación y Sistemas . 114 : 1–35. arXiv : 1811.03841 . doi :10.1016/j.jcss.2020.05.007.
8. Daskalakis, Constantinos; Papadimitriou, Christos (23 de enero de 2011). "Búsqueda local continua". Actas del vigésimo segundo simposio anual ACM-SIAM sobre algoritmos discretos : 790–804. doi :10.1137/1.9781611973082.62. ISBN 978-0-89871-993-2.S2CID2056144  .​
9. Klauck, Hartmut (1996). "Sobre la dificultad de la aproximación global y local". Actas del 5.º Taller escandinavo sobre teoría de algoritmos : 88-99.
10. Schäffer, Alejandro A.; Yannakakis, Mihalis (febrero de 1991). "Problemas de búsqueda local simples que son difíciles de resolver". Revista SIAM de Computación . 20 (1): 56–87. doi :10.1137/0220004.
11. Fiduccia, CM; Mattheyses, RM (1982). "Una heurística de tiempo lineal para mejorar las particiones de red". Actas de la 19.ª Conferencia de Automatización del Diseño : 175-181. ISBN 9780897910200.
12. Angel, Eric; Christopoulos, Petros; Zissimopoulos, Vassilis (2014). Paradigmas de optimización combinatoria: problemas y nuevos enfoques - Búsqueda local: complejidad y aproximación (2.ª ed.). John Wiley & Sons, Inc., Hoboken. págs. 435–471. doi :10.1002/9781119005353.ch14. ISBN 9781119005353.
13. Megiddo, Nimrod; Papadimitriou, Christos H (1991). "Sobre funciones totales, teoremas de existencia y complejidad computacional". Ciencias Informáticas Teóricas . 81 (2): 317–324. CiteSeerX 10.1.1.75.4797 . doi : 10.1016/0304-3975(91)90200-L . 
14. Krentel, M. (1 de agosto de 1990). "Sobre la búsqueda y verificación de soluciones óptimas locales". Revista SIAM de Computación . 19 (4): 742–749. doi :10.1137/0219052. ISSN  0097-5397.
15. Krentel, Mark W. (1989). "Estructura en soluciones localmente óptimas". 30.º Simposio anual sobre fundamentos de la informática . pp. 216–221. doi :10.1109/SFCS.1989.63481. ISBN 0-8186-1982-1. Número de identificación del sujeto  32686790.
16. Shimozono, Shinichi (1997). "Encontrar subgrafos óptimos mediante búsqueda local". Ciencias de la Computación Teórica . 172 (1): 265–271. doi : 10.1016/S0304-3975(96)00135-1 .
17. Dumrauf, Dominic; Süß, Tim (2010). "Sobre la complejidad de la búsqueda local para problemas de conjuntos estándar ponderados". CiE 2010: Programas, pruebas, procesos . Apuntes de clase en informática. Vol. 6158. Springer, Berlín, Heidelberg. págs. 132–140. CiteSeerX 10.1.1.762.6801 . doi :10.1007/978-3-642-13962-8_15. ISBN .  978-3-642-13961-1.S2CID14099014  .​
18. Papadimitriou, CH; Schäffer, AA; Yannakakis, M. (1990). "Sobre la complejidad de la búsqueda local". Actas del vigésimo segundo simposio anual de la ACM sobre teoría de la computación - STOC '90 . págs. 438–445. doi :10.1145/100216.100274. ISBN 0897913612.S2CID16877206  .​
19. Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004). "La complejidad de los equilibrios de Nash puros". Actas del trigésimo sexto simposio anual de la ACM sobre teoría de la computación . ACM. págs. 604–612. CiteSeerX 10.1.1.3.7861 . doi :10.1145/1007352.1007445. ISBN .  978-1581138528.S2CID 1037326  .
20. Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "Sobre el impacto de la estructura combinatoria en los juegos de congestión". J. ACM . 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913 . doi :10.1145/1455248.1455249. ISSN  0004-5411. S2CID  3070710. 
21. Yang, Yichen; Jia, Kai; Rinard, Martin (2022). "Sobre el impacto de la capacidad del jugador en los juegos de congestión". Teoría de juegos algorítmicos . Apuntes de clase en informática. Vol. 13584. págs. 311–328. arXiv : 2205.09905 . doi :10.1007/978-3-031-15714-1_18. ISBN . 978-3-031-15713-4.
22. Dumrauf, Dominic; Monien, Burkhard (2013). "Sobre la complejidad PLS de la asignación de máxima restricción". Theor. Comput. Sci . 469 : 24–52. doi : 10.1016/j.tcs.2012.10.044 . ISSN  0304-3975.
23. Kaznatcheev, Artem (2019). "Complejidad computacional como una restricción última en la evolución". Genética . 212 (1): 245–265. doi :10.1534/genetics.119.302000. PMC 6499524 . PMID  30833289. 
24. Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (19 de diciembre de 2022). "La complejidad del descenso de gradiente: CLS = PPAD ∩ PLS". Revista de la ACM . 70 (1): 7:1–7:74. arXiv : 2011.01929 . doi :10.1145/3568163. ISSN  0004-5411. S2CID  263706261.
25. Yannakakis, Mihalis (1 de mayo de 2009). "Equilibrios, puntos fijos y clases de complejidad". Computer Science Review . 3 (2): 71–85. arXiv : 0802.2831 . doi :10.1016/j.cosrev.2009.03.004. ISSN  1574-0137.