Hispanopedia Wiki
Articulo de referencia

PLS (complejidad)

En la teoría de la complejidad computacional , la búsqueda local polinomial ( PLS , por sus siglas en inglés) es una clase de complejidad que modela la dificultad de encontrar u...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la complejidad computacional , la búsqueda local polinomial ( PLS , por sus siglas en inglés) es una clase de complejidad que modela la dificultad de encontrar una solución localmente óptima a un problema de optimización . Las principales características de los problemas que pertenecen a PLS son que el costo de una solución se puede calcular en tiempo polinomial y el entorno de una solución se puede explorar en tiempo polinomial. Por lo tanto, es posible verificar si una solución es o no un óptimo local en tiempo polinomial. Además, dependiendo del problema y del algoritmo utilizado para resolverlo, podría ser más rápido encontrar un óptimo local que un óptimo global.

Descripción

Al buscar un óptimo local, surgen dos cuestiones interesantes: primero, cómo encontrarlo, y segundo, cuánto tiempo se tarda en encontrarlo. Para muchos algoritmos de búsqueda local, se desconoce si pueden encontrar un óptimo local en tiempo polinomial o no. [ 1 ] 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?". Esta clase contiene problemas de búsqueda local cuya optimalidad local puede verificarse en tiempo polinomial.

Un problema de búsqueda local pertenece al ámbito de la búsqueda local si se cumplen las siguientes propiedades:

  • El tamaño de cada solución está acotado polinómicamente en el tamaño de la instancia.I{\displaystyle I}.
  • Es posible encontrar alguna solución a una instancia de un 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óns{\displaystyle s}la mejor solución vecina o, si no existe tal mejor solución vecina, indique ques{\displaystyle s}es un óptimo local.

Ejemplo

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

Una solucións{\displaystyle s}para ese ejemplo es una cadena de bits que asigna cadaincógnitai{\displaystyle x_{i}}el valor 0 o 1. En este caso, una solución consta de 3 bits, por ejemplos=000{\displaystyle s=000}, que representa la asignación deincógnita1{\displaystyle x_{1}}aincógnita3{\displaystyle x_{3}}con el valor 0. El conjunto de solucionesFL(I){\displaystyle F_{L}(I)}es el conjunto de todas las asignaciones posibles deincógnita1{\displaystyle x_{1}},incógnita2{\displaystyle x_{2}}yincógnita3{\displaystyle x_{3}}.

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

El vecino Flip de una solucións{\displaystyle s}Se alcanza invirtiendo un bit de la cadena de bits.s{\displaystyle s}, así que los vecinos des{\displaystyle s}sonnorte(I,000)={100,010,001}{\displaystyle N(I,000)=\{100,010,001\}}con los siguientes costos:

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

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

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

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

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

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

Si simplemente contamos el número de cláusulas satisfechas, el problema se puede resolver en tiempo polinomial, ya que el número de costos posibles es polinomial. Sin embargo, si asignamos a cada cláusula un peso entero positivo (y buscamos maximizar localmente la suma de los pesos de las cláusulas satisfechas), el problema se vuelve PLS-completo (véase más adelante).

Definición formal

Un problema de búsqueda localL{\displaystyle L}tiene un conjuntoDL{\displaystyle D_{L}}instancias que se codifican utilizando cadenas sobre un alfabeto finitoΣ{\displaystyle \Sigma }. Para cada instanciaI{\displaystyle I}Existe un conjunto finito de soluciones.FL(I){\displaystyle F_{L}(I)}. DejarR{\displaystyle R}ser la relación que modelaL{\displaystyle L}. La relaciónR⊆DL×FL(I):={(I,s)∣I∈DL,s∈FL(I)}{\displaystyle R\subseteq D_{L}\times F_{L}(I):=\{(I,s)\mid I\in D_{L},s\in F_{L}(I)\}}está en PLS [ 2 ] [ 3 ] [ 4 ] si:

  • El tamaño de cada solucións∈FL(I){\displaystyle s\in F_{L}(I)}es polinomial acotado en el tamaño deI{\displaystyle I}
  • Casos de problemasI∈DL{\displaystyle I\in D_{L}}y solucioness∈FL(I){\displaystyle s\in F_{L}(I)}son verificables en tiempo polinomial
  • Existe una función computable en tiempo polinomial.A:DL→FL(I){\displaystyle A:D_{L}\rightarrow F_{L}(I)}que devuelve para cada instanciaI∈DL{\displaystyle I\in D_{L}}alguna solucións∈FL(I){\displaystyle s\in F_{L}(I)}
  • Existe una función computable en tiempo polinomial.B:DL×FL(I)→R+{\displaystyle B:D_{L}\times F_{L}(I)\rightarrow \mathbb {R} ^{+}}[ 5 ] que devuelve para cada solucións∈FL(I){\displaystyle s\in F_{L}(I)}de una instanciaI∈DL{\displaystyle I\in D_{L}}el costodoL(I,s){\displaystyle c_{L}(I,s)}
  • Existe una función computable en tiempo polinomial.norte:DL×FL(I)→PAGowmirsmit(FL(I)){\displaystyle N:D_{L}\times F_{L}(I)\rightarrow Powerset(F_{L}(I))}que devuelve el conjunto de vecinos para un par instancia-solución
  • Existe una función computable en tiempo polinomial.do:DL×FL(I)→norte(I,s)∪{OPAGT}{\displaystyle C:D_{L}\times F_{L}(I)\rightarrow N(I,s)\cup \{OPT\}}que devuelve una solución vecinas′{\displaystyle s'}con un mejor costo que la solucións{\displaystyle s}o afirma ques{\displaystyle s}es óptimo localmente
  • Por cada instanciaI∈DL{\displaystyle I\in D_{L}},R{\displaystyle R}contiene exactamente los pares(I,s){\displaystyle (I,s)}dóndes{\displaystyle s}es una solución óptima local deI{\displaystyle I}

Un ejemploDL{\displaystyle D_{L}}tiene la estructura de un grafo implícito (también llamado grafo de transición [ 6 ] ), siendo los vértices las soluciones con dos solucioness,s′∈FL(I){\displaystyle s,s'\in F_{L}(I)}conectados por un arco dirigido si y solo sis′∈norte(I,s){\displaystyle s'\in N(I,s)}.

Un óptimo local es una solucións{\displaystyle s}, que no tiene vecinos con mejores costos. En el grafo 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 ]

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 enterosnorte{\displaystyle n}ymetro{\displaystyle m}y dos circuitos booleanosS:{0,1}norte→{0,1}norte{\displaystyle S:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}de tal manera queS(0norte)≠0norte{\displaystyle S(0^{n})\neq 0^{n}}yV:{0,1}norte→{0,1,..,2metro−1}{\displaystyle V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}}, encontrar un vérticeincógnita∈{0,1}norte{\displaystyle x\in \{0,1\}^{n}}de tal manera queS(incógnita)≠incógnita{\displaystyle S(x)\neq x}y cualquieraS(S(incógnita))=S(incógnita){\displaystyle S(S(x))=S(x)}oV(S(incógnita))≤V(incógnita){\displaystyle V(S(x))\leq V(x)}.

Ejemplos de estructuras vecinales

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

  • Voltear [ 2 ] - El vecindario de una solucións=incógnita1,...,incógnitanorte{\displaystyle s=x_{1},...,x_{n}}se puede lograr negando (invirtiendo) un bit de entrada arbitrarioincógnitai{\displaystyle x_{i}}. Entonces, una solucións{\displaystyle s}y todos sus vecinosr∈norte(I,s){\displaystyle r\in N(I,s)}tener distancia de Hamming uno:H(s,r)=1{\displaystyle H(s,r)=1}.
  • Kernighan-Lin [ 2 ] [ 6 ] - Una soluciónr{\displaystyle r}es un vecino de la solucións{\displaystyle s}sir{\displaystyle r}se puede obtener des{\displaystyle s}mediante una secuencia de volteos codiciosos, donde ningún bit se voltea dos veces. Esto significa que, comenzando cons{\displaystyle s}, el vecino Flips1{\displaystyle s_{1}}des{\displaystyle s}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 malo) vecino des1{\displaystyle s_{1}}y así sucesivamente, hastasi{\displaystyle s_{i}}es una solución donde cada parte des{\displaystyle s}se niega. Tenga en cuenta que no está permitido volver a invertir un bit si ya se ha invertido.
  • k-Flip [ 9 ] - Una soluciónr{\displaystyle r}es un vecino de la solucións{\displaystyle s}si la distancia de HammingH{\displaystyle H}entres{\displaystyle s}yr{\displaystyle r}es como máximok{\displaystyle k}, entoncesH(s,r)≤k{\displaystyle H(s,r)\leq k}.

Ejemplos de estructuras de vecindad para problemas en grafos:

  • Intercambio [ 10 ] - Una partición(PAG2,PAG3){\displaystyle (P_{2},P_{3})} de nodos en un grafo es vecino de una partición(PAG0,PAG1){\displaystyle (P_{0},P_{1})}si(PAG2,PAG3){\displaystyle (P_{2},P_{3})}se puede obtener de(PAG0,PAG1){\displaystyle (P_{0},P_{1})}intercambiando un nodopag0∈PAG0{\displaystyle p_{0}\in P_{0}}con un nodopag1∈PAG1{\displaystyle p_{1}\in P_{1}}.
  • Kernighan-Lin [ 1 ] [ 2 ] - Una partición(PAG2,PAG3){\displaystyle (P_{2},P_{3})}es vecino de(PAG0,PAG1){\displaystyle (P_{0},P_{1})}si(PAG2,PAG3){\displaystyle (P_{2},P_{3})}se puede obtener mediante una secuencia codiciosa de intercambios de nodos enPAG0{\displaystyle P_{0}}con nodos enPAG1{\displaystyle P_{1}}Esto significa que los dos nodospag0∈PAG0{\displaystyle p_{0}\in P_{0}}ypag1∈PAG1{\displaystyle p_{1}\in P_{1}}se intercambian, donde la partición((PAG0∖pag0)∪pag1,(PAG1∖pag1)∪pag0){\displaystyle ((P_{0}\setminus p_{0})\cup p1,(P_{1}\setminus p_{1})\cup p_{0})}gana el mayor peso posible o pierde el menor peso posible. Tenga en cuenta que ningún nodo puede intercambiarse dos veces. Esta regla se basa en la heurística de Kernighan-Lin para la partición de grafos .
  • 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 elpag0∈PAG0{\displaystyle p_{0}\in P_{0}}con la mayor ganancia de costo, o la menor pérdida de costo, se intercambia porPAG1{\displaystyle P_{1}}, entonces el nodopag1∈PAG1{\displaystyle p_{1}\in P_{1}}con el mayor costo, o la menor pérdida de costo se cambia aPAG0{\displaystyle P_{0}}para reequilibrar las particiones. Los experimentos han demostrado que Fiduccia-Mattheyses tiene un tiempo de ejecución menor en cada iteración del algoritmo estándar, aunque a veces encuentra un óptimo local inferior.
  • FM-Swap [ 1 ] - Esta estructura de vecindario se basa en la estructura de vecindario de Fiduccia-Mattheyses. Cada solucións=(PAG0,PAG1){\displaystyle s=(P_{0},P_{1})}tiene un solo vecino, la partición obtenida después del primer intercambio de los Fiduccia-Mattheyses.

El algoritmo estándar

Consideremos el siguiente problema computacional : Dada alguna instanciaI{\displaystyle I}de un problema PLSL{\displaystyle L}encontrar una solución óptima locals∈FL(I){\displaystyle s\in F_{L}(I)}de tal manera quedoL(I,s′)≥doL(I,s){\displaystyle c_{L}(I,s')\geq c_{L}(I,s)}a pesar des′∈norte(I,s){\displaystyle s'\in N(I,s)}.

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

  1. UsarAL{\displaystyle A_{L}}para encontrar una solución inicials{\displaystyle s}
  2. Utilizar algoritmodoL{\displaystyle C_{L}}para encontrar una mejor solucións′∈norte(I,s){\displaystyle s'\in N(I,s)}. Si existe tal solución, reemplácelas{\displaystyle s}pors′{\displaystyle s'}y repita el paso 2, de lo contrario regreses{\displaystyle s}

Desafortunadamente, generalmente se necesita un número exponencial de pasos de mejora para encontrar un óptimo local, incluso si el problemaL{\displaystyle L}puede resolverse exactamente en tiempo polinomial. [ 2 ] No es necesario utilizar siempre 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 .

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

El espacio que necesita el algoritmo estándar es solo polinomial. Solo necesita guardar la solución actual.s{\displaystyle s}, que es polinomialmente acotado por definición. [ 1 ]

Reducciones

La reducción de un problema a otro puede utilizarse para demostrar que el segundo problema es al menos tan difícil como el primero. En particular, una reducción PLS se utiliza para probar que un problema de búsqueda local que pertenece a PLS también es PLS-completo, reduciendo un problema PLS-completo al problema que se pretende demostrar que es PLS-completo.

Reducción PLS

Un problema de búsqueda localL1{\displaystyle L_{1}}es PLS-reducible [ 2 ] a un problema de búsqueda localL2{\displaystyle L_{2}}si hay dos funciones de tiempo polinomialF:D1→D2{\displaystyle f:D_{1}\rightarrow D_{2}}ygramo:D1×F2(F(I1))→F1(I1){\displaystyle g:D_{1}\times F_{2}(f(I_{1}))\rightarrow F_{1}(I_{1})}de tal manera que:

  • siI1{\displaystyle I_{1}}es un ejemplo deL1{\displaystyle L_{1}}, entoncesF(I1){\displaystyle f(I_{1})}es un ejemplo deL2{\displaystyle L_{2}}
  • sis2{\displaystyle s_{2}}es una solución paraF(I1){\displaystyle f(I_{1})}deL2{\displaystyle L_{2}}, entoncesgramo(I1,s2){\displaystyle g(I_{1},s_{2})}es una solución paraI1{\displaystyle I_{1}}deL1{\displaystyle L_{1}}
  • sis2{\displaystyle s_{2}}es un óptimo local, por ejemploF(I1){\displaystyle f(I_{1})}deL2{\displaystyle L_{2}}, entoncesgramo(I1,s2){\displaystyle g(I_{1},s_{2})}tiene que ser un óptimo local, por ejemploI1{\displaystyle I_{1}}deL1{\displaystyle L_{1}}

Basta con mapear únicamente los óptimos locales deF(I1){\displaystyle f(I_{1})}a los óptimos locales deI1{\displaystyle I_{1}}y para mapear todas las demás soluciones, por ejemplo, a la solución estándar devuelta porA1{\displaystyle A_{1}}. [ 6 ]

Las reducciones PLS son transitivas . [ 2 ]

Reducción PLS ajustada

Definición de gráfico de transición

El gráfico de transición [ 6 ]TI{\displaystyle T_{I}}de una instanciaI{\displaystyle I}de un problemaL{\displaystyle L}es un grafo dirigido. Los nodos representan todos los elementos del conjunto finito de soluciones.FL(I){\displaystyle F_{L}(I)}y las aristas apuntan de una solución al vecino con un costo estrictamente mejor. Por lo tanto, es un grafo acíclico. Un sumidero, que es un nodo sin aristas salientes, es un óptimo local. La altura de un vérticev{\displaystyle v}es la longitud del camino más corto desdev{\displaystyle v}al sumidero más cercano. La altura del grafo 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.

Definición Reducción PLS estricta

Una reducción PLS(F,gramo){\displaystyle (f,g)}a partir de un problema de búsqueda localL1{\displaystyle L_{1}}a un problema de búsqueda localL2{\displaystyle L_{2}}es una reducción PLS ajustada [ 10 ] si para cualquier instanciaI1{\displaystyle I_{1}}deL1{\displaystyle L_{1}}, un subconjuntoR{\displaystyle R}de soluciones de ejemploI2=F(I1){\displaystyle I_{2}=f(I_{1})}deL2{\displaystyle L_{2}}Se puede elegir de manera que se cumplan las siguientes propiedades:

  • R{\displaystyle R}contiene, entre otras soluciones, todos los óptimos locales deI2{\displaystyle I_{2}}
  • Para cada soluciónpag{\displaystyle p}deI1{\displaystyle I_{1}}una soluciónq∈R{\displaystyle q\in R}deI2=F(I1){\displaystyle I_{2}=f(I_{1})}se puede construir en tiempo polinomial, de modo quegramo(I1,q)=pag{\displaystyle g(I_{1},q)=p}
  • Si el gráfico de transiciónTF(I1){\displaystyle T_{f(I_{1})}}deF(I1){\displaystyle f(I_{1})}contiene un camino directo desdeq{\displaystyle q}aq0{\displaystyle q_{0}}, yq,q0∈R{\displaystyle q,q_{0}\in R}pero todos los vértices del camino interno están fueraR{\displaystyle R}, luego para las soluciones correspondientespag=gramo(I1,q){\displaystyle p=g(I_{1},q)}ypag0=gramo(I1,q0){\displaystyle p_{0}=g(I_{1},q_{0})}sostiene cualquierapag=pag0{\displaystyle p=p_{0}}oTI1{\displaystyle T_{I_{1}}}contiene un borde depag{\displaystyle p}apag0{\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 esta puede ser reconocida 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 grafo es una solución válida, y la validez de una solución puede verificarse calculando sus vecinos y comparando los costos de cada uno con los de los demás.

También se ha demostrado que si un problema PLS es NP-difícil , entonces NP = co-NP . [ 2 ]

Completitud de PLS

Definición

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

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

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

Lista de problemas completos de PLS

Esta es una lista incompleta de algunos problemas conocidos que son PLS-completos. Los problemas aquí mencionados 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: Estructura Problema de optimización/Vecindad. Flecha punteada: Reducción PLS a partir de un problema.L{\displaystyle L}a un problemaQ:L←Q{\displaystyle Q:L\leftarrow Q}. Flecha negra: Reducción PLS ajustada. [ 4 ]

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 ajustada de Min/Max-circuit/Flip a Positive-not-all-equal-max-3Sat/Flip. Cabe señalar que Positive-not-all-equal-max-3Sat/Flip también puede reducirse a partir de Max-Cut/Flip. [ 10 ]
  • Se ha demostrado que Positive-not-all-equal-max-3Sat/Kernighan-Lin es PLS-completo mediante una reducción PLS ajustada 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 mediante 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 mediante una reducción PLS ajustada de Min-circuit/Flip a Min-4Sat-B/Flip. [ 9 ]
  • Se ha demostrado que Max-4Sat-B/Flip (o CNF-SAT) es PLS-completo mediante 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 mediante 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 mediante una reducción PLS ajustada de Max-Cut/Flip a Max-Uniform-Graph-partitioning/Swap. [ 10 ]
  • Se afirma que Max-Uniform-Graph-Partitioning /Fiduccia-Matheyses es PLS-completo sin demostración. [ 1 ]
  • Se ha demostrado que Max-Uniform-Graph-Partitioning /FM-Swap es PLS-completo mediante una reducción PLS ajustada 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 mediante una reducción PLS de Min/Max-circuit/Flip a Max-Uniform-Graph-Partitioning/Kernighan-Lin. [ 2 ] También existe una reducción PLS ajustada 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 mediante una reducción PLS ajustada 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 mediante una reducción PLS ajustada de Min-4Sat-B ′ /Flip a Min-Independent-Dominating-Set-B/k-Flip. [ 9 ]
  • Se afirma que Weighted-Independent-Set /Change 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 hereditaria general no trivial P mediante una reducción PLS ajustada 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 mediante una reducción PLS ajustada 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 mediante 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 mediante una reducción PLS ajustada de Max-2Sat/Flip a Metric-TSP/Lin-Kernighan. [ 18 ]
  • Se ha demostrado que Local-Multi-Processor-Scheduling /k-change es PLS-completo mediante una reducción PLS ajustada de Weighted-3Dimensional-Matching/(p, q)-Swap a Local-Multi-Processor-scheduling/(2p+q)-change, donde (2p + q) ≥ 8. [ 5 ]
  • Se ha demostrado que Selfish-Multi-Processor-Scheduling/k-change-with-property-t es PLS-completo mediante una reducción PLS ajustada de Weighted-3Dimensional-Matching/(p, q)-Swap a (2p+q)-Selfish-Multi-Processor-Scheduling/k-change-with-property-t, donde (2p + q) ≥ 8. [ 5 ]
  • Encontrar un equilibrio de Nash puro en un juego de congestión general /cambio ha demostrado ser PLS-completo mediante una reducción PLS ajustada de Positive-not-all-equal-max-3Sat/Flip a General-Congestion-Game/Change. [ 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 ajustada 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 asimétrico de congestión de red dirigida/cambio es PLS-completo mediante una reducción ajustada de Positive-not-all-equal-max-3Sat/Flip a juegos de congestión de red dirigida/cambio [ 19 ] y también mediante una reducción PLS ajustada de 2-Threshold-Games/Change a juegos de congestión de red dirigida/cambio. [ 20 ]
  • Se ha demostrado que encontrar un equilibrio de Nash puro en un juego asimétrico de congestión de red no dirigida/cambio es PLS-completo mediante una reducción PLS ajustada de juegos de 2 umbrales/cambio a juegos asimétricos de congestión de red no dirigida/cambio. [ 20 ]
  • Se ha demostrado que encontrar un equilibrio de Nash puro en un juego de congestión de red con distancia acotada simétrica es PLS-completo mediante una reducción PLS ajustada de juegos de 2 umbrales a juegos de congestión de red con distancia acotada simétrica. [ 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 ajustada de Max-Cut/Flip a un juego/cambio de 2 umbrales. [ 20 ]
  • Se ha demostrado que encontrar un equilibrio de Nash puro en el juego/cambio de reparto de mercado con costes acotados polinomiales es PLS-completo mediante una reducción PLS ajustada de juegos/cambio de 2 umbrales a juego/cambio de reparto de mercado. [ 20 ]
  • Se ha demostrado que encontrar un equilibrio de Nash puro en un diseño/cambio de red superpuesta es PLS-completo mediante una reducción de juegos/cambios de 2 umbrales a diseño/cambio de red superpuesta. De forma análoga a la demostración del juego/cambio de congestión de red dirigida asimétrica, la reducción es precisa. [ 20 ]
  • Se ha demostrado que Min-0-1-Integer Programming /k-Flip es PLS-completo mediante una reducción PLS ajustada de Min-4Sat-B ′ /Flip a Min-0-1-Integer Programming/k-Flip. [ 9 ]
  • Se afirma que Max-0-1-Integer Programming /k-Flip es PLS-completo debido a la reducción PLS a Max-0-1-Integer Programming/k-Flip, pero se omite la prueba. [ 9 ]
  • Asignación de restricción máxima (p, q, r)
    • Se ha demostrado que (3, 2, 3)-Max-Constraint-Assignment-3-partite/Change es PLS-completo mediante una reducción PLS ajustada 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 mediante una reducción PLS ajustada 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 mediante una reducción ajustada 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 mediante una reducción PLS desde Max-circuit/Flip. [ 15 ] Se afirma que la reducción puede extenderse para obtener la rigidez. [ 22 ]
  • Se ha demostrado que Nearest-Colorful-Polytope/Change es PLS-completo mediante 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 ajustada de Max-Cut/Flip a configuración estable/inversión. [ 1 ] [ 10 ] [ 18 ]
  • Se ha demostrado que Weighted-3Dimensional-Matching /(p, q)-Swap es PLS-completo para p ≥9 y q ≥ 15 mediante una reducción PLS ajustada de (2, 3, r)-Max-Constraint-Assignment-2-partite/Change a Weighted-3Dimensional-Matching /(p, q)-Swap. [ 5 ]
  • El problema Real-Local-Opt (encontrar el óptimo local ɛ de una función objetivo continua λ-Lipschitz)V:[0,1]3→[0,1]{\displaystyle V:[0,1]^{3}\rightarrow [0,1]}y una función vecinalS:[0,1]3→[0,1]3{\displaystyle S:[0,1]^{3}\rightarrow [0,1]^{3}}) es PLS-completo. [ 8 ]
  • Encontrar un pico de aptitud local en paisajes de aptitud biológica especificados por el modelo NK /mutación puntual con K ≥ 2 se demostró que es 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 (Búsqueda Local Continua) es igual a la intersección de PPAD y PLS.

Lecturas adicionales

  • Equilibrios, puntos fijos y clases de complejidad: una revisión. [ 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. 1 2 3 4 5 6 7 8 9 10 11 12 Yannakakis, Mihalis (2003). Búsqueda local en optimización combinatoria: complejidad computacional . Princeton University Press. págs. 19–55 . ISBN  9780691115221.
  2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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. 1 2 Mulzer, Wolfgang; Stein, Yannik (14 de marzo de 2018). "Aspectos computacionales del teorema de Carathéodory colorido". Geometría discreta y computacional . 60 (3): 720– 755. arXiv : 1412.3347 . Bibcode : 2014arXiv1412.3347M . doi : 10.1007/s00454-018-9979-y . S2CID 254024141 . 
  4. 1 2 Borzechowski, Michaela. "La clase de complejidad Búsqueda Local Polinomial (PLS) y problemas PLS-completos" (PDF) .
  5. 1 2 3 4 Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009). "La programación multiprocesador es PLS completa" . Ciencias de Sistemas, 2009. HICSS'09. 42.a Conferencia Internacional de Hawái del : 1 al 10.
  6. 1 2 3 4 5 6 7 Michiels, 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). "Extremo único de una línea potencial" . Journal of Computer and System Sciences . 114 : 1–35 . arXiv : 1811.03841 . doi : 10.1016/j.jcss.2020.05.007 .
  8. 1 2 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 . hdl : 1721.1/73982 . ISBN 978-0-89871-993-2. S2CID 2056144 . 
  9. 1 2 3 4 5 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. 1 2 3 4 5 6 7 8 9 Schäffer, Alejandro A.; Yannakakis, Mihalis (febrero de 1991). "Problemas de búsqueda local simples que son difíciles de resolver". SIAM Journal on Computing . 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. pp. 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" . Theoretical Computer Science . 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 cómo encontrar y verificar soluciones óptimas locales". SIAM Journal on Computing . 19 (4): 742– 749. doi : 10.1137/0219052 . ISSN 0097-5397 . 
  15. 1 2 3 Krentel, Mark W. (1989). "Estructura en soluciones localmente óptimas" . 30.º Simposio Anual sobre Fundamentos de la Informática . págs. 216–221 . doi : 10.1109/SFCS.1989.63481 . ISBN  0-8186-1982-1. S2CID 32686790 . 
  16. ↑ Shimozono, Shinichi (1997). "Finding optimal subgraphs by local search" . Theoretical Computer Science . 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 . Notas de clase en informática. Vol. 6158. Springer, Berlín, Heidelberg. pp. 132–140 . CiteSeerX 10.1.1.762.6801 . doi : 10.1007/978-3-642-13962-8_15 . ISBN    978-3-642-13961-1. S2CID 14099014 . 
  18. 1 2 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. S2CID 16877206 . 
  19. 1 2 3 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. 1 2 3 4 5 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ítmica . Notas de clase en ciencias de la computación. Vol. 13584. pp. 311–328 . arXiv : 2205.09905 . doi : 10.1007/978-3-031-15714-1_18 . ISBN   978-3-031-15713-4.
  22. 1 2 3 4 Dumrauf, Dominic; Monien, Burkhard (2013). "Sobre la complejidad PLS de la asignación de restricciones máximas" . Theor. Comput. Sci . 469 : 24–52 . doi : 10.1016/j.tcs.2012.10.044 . ISSN 0304-3975 . 
  23. ↑ Kaznatcheev, Artem (2019). "Complejidad computacional como restricción última de la evolución" . Genetics . 212 ( 1): 245– 265. doi : 10.1534/genetics.119.302000 . PMC 6499524. PMID 30833289 .  
  24. ↑ Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "La complejidad del descenso de gradiente: CLS = PPAD ∩ PLS" . Journal of the ACM . 70 (1): 7:1–7:74. arXiv : 2011.01929 . doi : 10.1145/3568163 . ISSN 0004-5411 . S2CID 263706261 .  
  25. ↑ Yannakakis, Mihalis (2009-05-01). "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 .