¿Qué tan difícil es contar el número de óptimos locales para un problema en PLS?

Para un problema de búsqueda local polinómica , sabemos que debe existir al menos una solución (óptimo local). Sin embargo, podrían existir muchas más soluciones, ¿qué tan difícil es contar la cantidad de soluciones para un problema PLS completo? Estoy particularmente interesado en el problema de decisión: ¿la instancia de este problema PLS-complete tiene dos o más soluciones?

¿La complejidad depende de qué problema PLS-complete elijamos? Si es así, estaría particularmente interesado en 2SAT ponderado (como se define en [SY91] y [Rou10]). Sé que contar el número de soluciones satisfactorias para 2SAT es # P-completo, pero a primera vista parece que los óptimos locales de 2SAT ponderado y las soluciones para 2SAT no tienen mucho en común.

También sé que para el primo PPAD de PLS, [CS02] muestra que contar el número de equilibrios de Nash es # P-duro. Esto sugiere que problemas similares de PLS, como contar el número de equilibrios de estrategia pura en juegos de congestión, también serían difíciles.

Referencias

[CS02] Conitzer, V. y Sandholm, T. (2002). La complejidad resulta sobre los equilibrios de Nash. IJCAI-03 . cs / 0205074 .

[Rou10] T. Roughgarden. (2010) Equilibrios computacionales: una perspectiva de complejidad computacional. Economic Theory , 42: 193-236.

[SY91] AA Schaeffer y M. Yannakakis. (1991) Problemas simples de búsqueda local que son difíciles de resolver. SIAM Journal on Computing , 20 (1): 56-87.

Puedo responder parcialmente a su pregunta: contar los óptimos locales de un problema de búsqueda completa de PLS puede ser realmente # P-difícil.

Primero, como señala Yoshio, hay un problema de búsqueda en PLS cuyo problema de conteo asociado es # P-completo. ( Sin embargo, no sabemos si es PLS completo). Sea un problema de PLS completo. Luego defina que, en la entrada para , solicita un óptimo local para la entrada con respecto a . Este problema hereda la membresía PLS de , hereda la integridad de PLS de , y para el problema de conteo hereda la integridad de # P de .$P_1$$P_1$$P_2$$P'$$(x, i)$$i \in \{1, 2\}$$x$$P_i$$P_1, P_2$$P_2$$P_1$

Del mismo modo, se puede construir un problema (artificial) de PLS completo para el cual es NP completo para decidir si hay más de un óptimo local. Como en el argumento anterior, uno "engrapa" un problema de PLS completo como antes, con un problema de PLS que, al ingresar una fórmula booleana , tiene más de un óptimo local asociado iff es satisfactoria.$P_1$$P_2$$\psi$$\psi$

Este tipo de construcciones son algo insatisfactorias porque estamos tratando de construir un problema de búsqueda que tenga dos propiedades de dureza, pero el dominio de "se divide" en dos partes, cada una de las cuales puede tener solo una de las dos propiedades. A continuación, mostraré cómo, dado un problema de búsqueda en PLS cuyo problema de conteo asociado es # P-complete, y dado un problema de PLS-complete , se puede definir un problema de PLS que es tan difícil como contar tanto para como para busque de manera "instancia por instancia".$Q$$Q$$P_1$$P_2$$Q$$P_1$$P_2$

Es decir, exhibiremos tal manera que resolver el problema de conteo para en la entrada reduce de manera eficiente a resolver el problema de conteo para en la entrada , y el problema de búsqueda para en la entrada reduce al problema de búsqueda de en la entrada .$Q$$P_1$$x$$Q$$x$$P_2$$x$$Q$$x$

Para simplificar la presentación, suponemos que son tales que en cualquier entrada de longitud , el espacio de solución candidato asociado con está sobre las cadenas de bits de longitud para alguna (pero con diferentes estructuras vecinas para ). Deje ser la función de aptitud asociada con .$P_1, P_2$$x$$n$$x$$y$$n^c$$c$$P_1, P_2$$F_i(x, y)$$P_i$

En la entrada , el espacio de búsqueda para está sobre tuplas donde cada está en , y . Como la función de aptitud para , definimos$x \in \{0, 1\}^n$$Q$$(y^1, y^2, z, b)$$y^i$$\{0, 1\}^{n^c}$$z \in \{0, 1\}^{n^c + 1}$$b \in \{0, 1\}$$F(x, (y^1, y^2, z, b))$$Q$

$F(x, (y^1, y^2, z, b)) := F_1(x, y^1) + F_2(x, y^2)$ si , $b = 1$

$F(x, (y^1, y^2, z, b)) := ||y^1|| + ||z|| + F_2(x, y^2)$ si .$b = 0$

(Eso es el peso de Hamming arriba).

Para la estructura de vecindad de , conectamos cada tupla (con ) a todas las tuplas tal que$Q$$(x, (y^1, y^2, z, 1))$$b = 1$$(x, ((y')^1, (y')^2, z', 1))$

(A) está conectado a acuerdo con para , Y$(x, y^i)$$(x, (y')^i)$$P_i$$i = 1, 2$

(B) difieren en como máximo 1 coordenada.$z, z'$

Para tuplas con , conectamos a todas las tuplas tal que$b = 0$$(x, (y^1, y^2, z, 0))$$(x, ((y')^1, (y')^2, z', 0))$

(A ') está conectado a acuerdo con , Y$(x, y^2)$$(x, (y')^2)$$P_2$

(B ') difieren en como máximo 1 coordenada, al igual que .$z, z'$$y^1, (y')^1$

(Tenga en cuenta que las tuplas con están desconectadas de las que tienen ).$b = 0$$b = 1$

Esa es la definición de . Los barrios son de tamaño polinómico según sea necesario, por lo que está en PLS. $Q$$Q$

Reclamación: Los valores óptimos locales para la longitud entrada acuerdo con son exactamente los siguientes dos conjuntos disjuntos:$n$$x$$Q$

(1) todas las tuplas , donde es un óptimo local de para cada uno de (y es arbitrario y ); y,$(x, (y^1, y^2, z,1))$$(x, y^i)$$P_i$$i = 1, 2$$z$$b = 1$

(2) todas las tuplas , donde es un óptimo local de , y donde son ambos todos-1 y .$(x, 1^{n^c}, y^2, 1^n, 0))$$(x, y^2)$$P_2$$z, y^1$$b = 0$

Si está de acuerdo, entonces la dureza PLS de es inmediata, ya que cualquier óptimo local de para la entrada da un óptimo local de (para la misma entrada ), y es PLS-hard.$Q$$(x, (y^1, y^2, z,b))$$Q$$x$$(x, y^2)$$P_2$$x$$P_2$

Además, de nuestro reclamo se deduce que el número de óptimos locales para bajo es igual a , donde es el número de óptimos locales para bajo . Ahora está en el rango , entonces tenemos$N(x)$$x$$Q$$(2^{n^c + 1} N_1(x) + 1) \cdot N_2(x)$$N_i(x)$$x$$P_i$$N_2(x)$$[1, 2^{n^c}]$

$N_2(x) = N_2(x)$ mod mod mod .$2^{n^c + 1} = (2^{n^c + 1} N_1(x) + 1) \cdot N_2(x)$$2^{n^c + 1} = N(x)$$2^{n^c + 1}$

Entonces podemos obtener dado . Entonces también podemos obtener , por álgebra simple: . Como es # P-completo para calcular, también lo es . Por lo tanto, es # P-complete contar óptimos locales para (y contar para reduce a contar para en la misma instancia). $N_2(x)$$N(x)$$N_1(x)$$N_1(x) = \left(\frac{N(x)}{N_2(x)} - 1\right)/2^{n^c + 1}$$N_1(x)$$N(x)$$Q$$P_1$$Q$

No sé cómo ofrecer una reducción para combinar la dureza PLS con la dureza NP para decidir la unicidad de los óptimos locales de una manera "instancia por instancia".

En cuanto a si cada problema de búsqueda completa de PLS produce un problema de conteo # P-completo, tampoco lo sé. Se parece relacionado con la cuestión de si, para cada problema NP-completo decisión de L y cada polytime verificador de , el problema testigo de recuento asociado es # P-completo. # La integridad de P se cumple en todos los casos específicos que las personas han considerado, y en algunas condiciones razonablemente leves, pero en general está abierto. Ver esta discusión .$V(x, y)$$L$

Para un problema específico y más natural sabe que es PLS completo, uno podría establecer la integridad de # P para contar los óptimos locales al dar una reducción de PLS de decir Matching to que tiene algunas propiedades especiales apropiadas para contar. Quizás las técnicas existentes son suficientes; No he tratado de averiguarlo.$Q$$Q$

Considere el problema de coincidencia máxima en gráficos bipartitos. La familia de soluciones factibles consiste en todas las coincidencias, y la búsqueda local se realiza mediante la búsqueda de rutas de aumento. El problema pertenece a PLS ya que se puede encontrar una ruta de aumento en el tiempo polinomial si una coincidencia actual no es máxima, y ​​la máxima puede verificarse en tiempo polinomial. Cualquier óptimo local es una coincidencia máxima (es decir, óptimo global). Sin embargo, es # P-difícil calcular el número de coincidencias máximas en un gráfico bipartito.

Dado que se puede encontrar un óptimo local en el tiempo polinómico, es poco probable que el problema sea completo con PLS. Por lo tanto, me temo que esta no es una respuesta prevista (su pregunta se limita a problemas de PLS completo). Sin embargo, debo señalar que contar el número de óptimos locales puede ser difícil a pesar de que un óptimo local se puede encontrar de manera eficiente.