Un interesante problema de optimización

Question

Se le dan n números enteros no negativos $a_1, a_2 ,, a_n$ . En una sola operación, se toman dos enteros cualesquiera de estos enteros y se sustituyen por un nuevo entero cuyo valor es igual a la diferencia entre esos enteros; es decir, si los enteros eliminados son $b$ y $c$ , pones $|b - c|$ en el plató de nuevo. Sigue aplicando la operación hasta que te quedes con un solo número. Así, después de $n - 1$ pasos el juego terminará; tienes que averiguar cuál es el valor máximo del único número que queda al final.

Estoy interesado en ver cualquier algoritmo de tiempo polinómico para el problema. Actualmente no tengo ninguna idea acerca de cómo resolver este problema en menos de $\mathcal{O}(n !)$ .

Si cree que no existe ningún algoritmo de tiempo polinómico, ¿podría establecer en qué clase de complejidad se encuentra? ¿Es NP completo?

Resumen de los principales argumentos:

1. Nunca se puede obtener más del máximo de $a_i$ 's.
2. Parece que el número de valores diferentes de los terminales son como máximo $2^{n - 2}$ .
3. No todas las expresiones son válidas. Una expresión corresponde a una combinación de signos + y - asignados a enteros de la matriz.
4. Mantener la diferencia $\geq$ 0 es la principal fuente de dificultades.
5. Si suponemos que todas las expresiones son válidas, entonces este problema se puede convertir en un problema NP completo: el problema SUBSET-SUM. Pero como no todas las expresiones son válidas, esto nos puede dar mejores ideas/algoritmos.
6. Bill Bradley ha demostrado que el problema de encontrar el mínimo es NP-difícil y también ha mostrado la construcción para el punto 2; el problema de encontrar el número de posiciones terminales diferentes fue planteado por Johan Wästlund.
7. El comentario de Brendan McKay amplía el argumento para encontrar el máximo también es NP duro. Por lo tanto actualmente hemos conseguido demostrar que el problema es NP duro .

Answer 1

[Editar: Yo había publicado originalmente una prueba de que encontrar el mínimo era NP-difícil; en los comentarios más abajo, Brendan McKay señaló cómo convertir eso en una prueba de que encontrar el valor de máximo es NP-difícil, que era la pregunta formulada por el autor original. He editado esto para incluir una respuesta completa a la pregunta original].

Vamos a referirnos a la operación de sustitución de dos valores $b,c$ en un multiconjunto por el valor único $|b-c|$ como una "contracción"; el cartel original pregunta si es posible encontrar una ordenación de contracciones repetidas que maximice el valor final.

En este post, empezamos preguntándonos si podemos encontrar el orden con el mínimo valor posible. En concreto, tratamos de determinar si el valor mínimo es cero o mayor que cero. Demostraremos que decidir esta cuestión es NP-completo. (Tenemos que convertirlo en un problema de decisión ("¿es igual a cero?") en lugar de un problema de minimización ("¿cuál es el valor mínimo?") para expresarlo en términos de NP-completitud). A continuación, mostramos cómo convertir este resultado en una declaración sobre el valor máximo en lugar del mínimo.

Además, al comentario de Johan Wastlund más arriba, una ligera modificación de la construcción da un $O(2^{n-2})$ inferior en el número máximo de valores distintos que se pueden producir (que esbozaré al final).

---

Determinar si el valor mínimo es cero está claramente en NP-- podemos simplemente (no determinísticamente) adivinar el patrón correcto de pasos para producir cero. Demostrar que es NP-completo requiere un poco más de esfuerzo. Lo demostraremos mediante una reducción a partir del problema de partición .

Tomemos una instancia del problema de partición con entradas $x_1,...,x_n$ . Estamos tratando de encontrar un subconjunto $S\subseteq \{1,...,n\}$ tal que $\sum_{i\in S}x_i=\sum_{i\not\in S}x_i$ .

Establecer $M_1=M_2=2\sum_i x_i$ . Consideremos el multiconjunto $\{M_1,M_2,x_1,...,x_n\}$ . Sea $f(x,y)=|x-y|$ . Puesto que hemos tomado $M_1$ sea tan grande, se deduce que

$$f(\cdots(f(f(M_1,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_1-\sum_{j=1}^k x_{i_j}$$

y análogamente para $M_2$ .

Afirmación: si existe un subconjunto $S$ que divide los números enteros $x_1,...,x_n$ entonces el valor mínimo alcanzado por las contracciones repetidas es cero.

Prueba: Supongamos que tal $S$ existe. Entonces podemos aplicar $f$ a $M_1$ y los elementos de $S$ para obtener

$$M_1-\sum_{i\in S}x_i$$

y de forma similar con $M_2$ y el complemento de $S$ para obtener

$$M_1-\sum_{i\not\in S}x_i$$

Como último paso, podemos restarlos y obtener cero. Dado que el valor de salida es no negativo, entonces el valor mínimo es cero.

Afirmación: si una ordenación de contracciones repetidas produce un valor final de cero, entonces podemos producir una partición a partir de esta ordenación en tiempo polinómico.

Prueba: El cálculo del valor final alcanzado por la contracción repetida corresponde a la evaluación de $f$ en un árbol binario con los nodos hoja etiquetados por $x_1,...,x_n$ . Como se ha señalado en los comentarios anteriores, podemos "aplastar" este árbol (en $O(n)$ tiempo) y demostrar que la salida es igual a la suma $\sum_i \pm x_i$ . Si dejamos que $S$ corresponden al $x_i$ con un índice positivo, hemos construido la partición deseada.

---

Hemos demostrado anteriormente que determinar si el valor más pequeño es cero es NP-completo. Ahora mostramos que esto implica la misma complejidad para el máximo.

En concreto, tome $x_1,...,x_n$ y observe que el valor máximo posible que puede alcanzarse mediante una contracción repetida es $\max_i x_i$ . Ahora nos preguntamos: ¿es el valor final máximo alcanzado por la contracción repetida igual a $\max_i x_i$ ¿o es estrictamente más pequeño?

Demostraremos que decidir esta cuestión es NP-completo. Es claramente en NP, ya que podemos exhibir un ordenamiento de las contracciones que logra el máximo, si tal ordenamiento existe.

Para demostrar que es NP-completo, reduciremos a partir del problema de determinar si existe un ordenamiento de contracciones repetidas que sea igual a cero.

Tomemos el multiconjunto $A=\{x_1,...,x_n\}$ y considerar un nuevo elemento $M=1+\sum_i x_i$ . Sea $B=A\cup \{M\}$ . Tenga en cuenta que $M$ es el máximo único sobre $B$ .

Primero demostramos que si el valor final máximo para la contracción repetida de $B$ es $M$ entonces la contracción repetida mínima de $A$ es 0. Si existe una contracción repetida con suma final $M$ entonces cualquier contracción que implique $M$ debe ser de la forma $f(M,0)$ (de lo contrario, la suma final sería estrictamente inferior a $M$ ) y viceversa. Supongamos que sustituimos $M$ por 0; el mismo patrón de contracciones producirá ahora un valor final de 0. Por lo tanto, hemos producido un patrón de contracciones en $A\cup \{0\}$ que da un valor final de cero.

En la otra dirección, demostramos que si el valor final mínimo para la contracción repetida de $A$ es 0, entonces el valor máximo de $B$ es $M$ . Supongamos que la contracción repetida mínima de $A$ es 0. Consideremos entonces el mismo patrón de contracciones en $B$ lo que nos dejará con $M$ y 0; la última contracción producirá $|M-0|=M$

Por lo tanto, podemos determinar si el valor final mínimo de $A$ (que era arbitraria) es cero si y sólo si podemos determinar si el valor final máximo de $B$ es $M$ .

Por lo tanto, el problema de determinar si el valor final máximo de una contracción repetida es igual al máximo del conjunto original es NP-completo.

---

Johan Wastlund preguntó, en función de $n$ cuál es el número máximo de valores distintos que se pueden producir aplicando $f$ en todas las combinaciones posibles? Sugirió que podría ser $2^{n-2}$ . La construcción anterior puede modificarse para demostrar que hay al menos esta cantidad de posibilidades.

Sea $x_i=2^i$ para $i=1,...,n-2$ . Sea $M_1=2^{n-1}$ y que $M_2=2^n$ . Desde

$$M_z>\sum_{i=1}^{n-2}$$

(para $z=1,2$ ), seguimos teniendo $$f(\cdots(f(f(M_z,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_z-\sum_{j=1}^k x_{i_j}$$

Sea $S$ sea el subconjunto de índices restados de $M_1$ . Entonces podemos construir la suma $$f(M_1-\sum_{i\in S}^k x_{i},M_2-\sum_{i\not\in S}^k x_{i})= M_2-M_1+(\sum_{i\in S}^k x_{i})-(\sum_{i\not\in S}^k x_{i})$$

Esta suma asume un valor distinto para cada subconjunto $S$ de $\{1,...,n-2\}$ por lo que hay al menos $2^{n-2}$ valores distintos.

Answer 2

Esto iba a ser un comentario, pero no tengo suficiente reputación para publicar uno. Espero que también tenga algo que ver con una respuesta (pero no recuerdo qué significa tiempo polinómico).

Supongamos por comodidad $a_1 \leq a_2 \leq ... \leq a_{n-1} \leq a_n$ . Sea $m$ denotan el valor máximo del número al final del juego. Es evidente que $m$ es como máximo $a_n$ . Podríamos considerar un doble problema: Guardar $a_n$ a un lado, y con los números restantes $a_1 \leq a_2 \leq ... \leq a_{n-1}$ jugar al mismo juego, pero esta vez intentando acabar con el el más pequeño número posible. Digamos que el número más pequeño es $s$ por lo que ahora tenemos $m = a_n - s$ . Una idea de cómo conseguir $s$ sería la siguiente: Es de la forma (valor abs de) $a_{n-1}+e_{n-2}a_{n-2}+...+e_2 a_2 + e_1 a_1$ donde $e_j=-1$ si la suma parcial anterior es positiva (por lo que pretendemos disminuirla aún más), o bien $e_j=1$ si la suma parcial precedente es negativa (pretendemos que se aproxime más a $0$ ). Sólo una idea, no he verificado todos los detalles, significaba un comentario.

Permítanme ilustrar (ya que el significado de suma parcial anterior puede no estar claro). Digamos que empezamos con $[2,7,17,19,35]$ . Guardar $35$ a un lado y con los números restantes formar $19-17-7+2$ (el $+2$ al final porque $19-17-7=-5<0$ y queremos que el $-5$ para acercarse a $0$ ). Así, $19-17-7+2 = -3$ o (tomando el valor abs) $s=3$ . Finalmente $m=35-3=32$ . Si en cambio sigo los pasos del juego, quedaría así: $[2,7,17,19,35]$ , $[2,7,2,35]$ , $[2,5,35]$ , $[3,35]$ , $[32]$ .