¿Es difícil encontrar cadenas de adición óptimas?

Una cadena de suma es una secuencia de enteros positivos donde y cada índice , tenemos para algunos índices . La longitud de la cadena de adición es ; El objetivo de la cadena de suma es .x 1 = 1 i ≥ 2 x i = x j + x k 1 ≤ j , k < i $(x_1, x_2, \dots, x_n)$$x_1 = 1$$i\ge 2$$x_i = x_j + x_k$$1\le j,k < i$$n$$x_n$

Lo que se sabe sobre la complejidad del siguiente problema: Dado un número entero , ¿cuál es la longitud de la cadena de adición más corta cuyo objetivo es ? ¿Es NP-duro?$N$$N$

Wikipedia señala un artículo de 1981 de Downey, Leong y Sethi que demuestra que el siguiente problema relacionado es NP-hard: Dado un conjunto de enteros, ¿cuál es la longitud mínima de una cadena de suma que incluye todo el conjunto? Aparentemente, varios autores afirman que este documento demuestra que el problema de un solo objetivo es NP-duro, pero no lo es.

El problema se menciona como abierto en la tesis doctoral de Eric Lehman "Algoritmos de aproximación para la compresión de datos basada en la gramática" en 2002. De la p35 de la tesis:

"Sin embargo, una solución exacta al problema de la cadena de adición sigue siendo extrañamente difícil de alcanzar. El método M-ary se ejecuta en el tiempo polylog (n) y proporciona una aproximación 1 + o (1). Sin embargo, incluso si se permite exponencialmente más tiempo, poly ( n), no se conoce un algoritmo exacto ".

Y en el artículo principal de la tesis de Lehman, hay una buena visión general del problema (sección VB) con referencias.

Me gustaría documentar algún progreso parcial, aparentemente prometedor hasta ahora, hacia un algoritmo de tiempo polinómico. ACTUALIZACIÓN : se agregaron algunos detalles para dar cuenta de una falla señalada por @David (¡gracias!).

El enfoque consiste en reducir esto a una instancia de CSP de MIN-ONES EVEN-3 (MOEC), que resulta ser un problema de tiempo polinómico solucionable. La prueba de la reducción es un poco confusa, ¡pero espero que exista!

Una instancia de MOEC es una familia de subconjuntos de tamaños de un universo de variables y un entero . La pregunta es si existe una asignación satisfactoria de peso como máximo , donde una asignación es una función del universo a , el peso de una asignación es el número de variables que le asigna una, y un la asignación es satisfactoria si, para cada subconjunto de variables , la asignación (digamos ) tiene la propiedad de que:k k { 0 , 1 } { x , y , z } $3$$k$$k$$\{0,1\}$$\{x,y,z\}$$f$

$f(x) + f(y) + f(z) = 0 (mod ~~2)$ .

Podrías visualizar esto como 3-SAT con una noción diferente de satisfacción: elige ninguno o elige dos. Seré un poco laxo con respecto a la instancia de MOEC, ya que permitiré, además de los subconjuntos habituales , implicaciones, disyunciones de longitud dos y la restricción . Creo que estas simples adiciones mantendrán el problema del tiempo polinómico.( x = 1 $3$$(x = 1)$

Digamos que estamos reduciendo el problema de la cadena de suma para el número . La variable establecida para esta reducción es la siguiente:$n$

Por cada , la variable . Voy a volver a escribir la variable como . Para cada par tal que , introduzca las variables y . N i N n N i , j 1 ≤ i , j ≤ k P i j Q i $1 \leq i \leq n$$N_i$$N_n$$N$$i,j$$1 \leq i,j \leq k$$P_{ij}$$Q_{ij}$

Introduzca los siguientes subconjuntos, para cada tal que :k = i + $i,j,k$$k = i+j$

$\{P_{ij}, Q_{ij}, N_k \}$

y las siguientes implicaciones:

P i j ⇒ N $P_{ij} \Rightarrow N_i$ y $P_{ij} \Rightarrow N_j$

y las siguientes restricciones:

$(N_1 = 1), (N = 1)$ .

Finalmente, necesitamos agregar restricciones que aseguren que se elija al menos una de las variables cuando se asigna una variable "correspondiente" (perdona el abuso de notación). Esto se puede hacer agregando la restricción OR habitual sobre todo modo que sume a la variable en cuestión. Sin embargo, tenemos que encontrar una manera de volver a codificar esto en MOEC-framework.N P i j i + j $P$$N$$P_{ij}$$i + j$$N$

Entonces permítanme describir una forma general de decir, dado un conjunto de variables:

$(X, l_1, l_2, \ldots, l_t)$ ,

cómo la restricción "si una asignación es satisfactoria y establece en uno, entonces exactamente uno de los debe establecerse en uno por la asignación", puede codificarse con la sintaxis MOEC. Tenga en cuenta que esto es suficiente para nuestros requisitos, simplemente presentamos las restricciones:l $X$$l_i$

$(N_k, \{ P_{ij} ~|~ i + j = k \})$ .

La codificación se realiza de la siguiente manera. Deje que sea ​​el árbol binario completo enraizado en hojas. Introduzca una nueva variable para todos y , donde denota el número de nodos de a profundidad . t T d i 1 ≤ d ≤ log t 1 ≤ i ≤ L ( d ) L ( d ) T X$T_X$$t$$T_{di}$$1 \leq d \leq \log t$$1 \leq i \leq {\cal L}(d)$${\cal L}(d)$$T_X$$d$

Para cada nodo , si y sean sus hijos en el árbol, introducir el AÚN 3-restricción:$T_{di}$$p$$q$

$\{T_{di},p,q\}$

Esto significa que si una variable correspondiente a un nodo se establece en verdadero, entonces exactamente uno de sus hijos también debe establecerse en verdadero. Ahora agregue las implicaciones:

$(X \Rightarrow T_{11})$ y (coma para mayor claridad).$(d_{\log t,j}) \Rightarrow l_j$

Esta combinación de restricciones e implicaciones EVEN-3 es equivalente a la restricción que deseamos codificar.

Intuitivamente, lo que sucede es que las dos últimas restricciones desencadenan exactamente las reacciones necesarias para construir una cadena de adición. En particular, echemos un vistazo a los que se asignan a uno por una asignación satisfactoria: la afirmación es que formarán una cadena de adición para : dado que la asignación se ve obligada a establecer en uno, debe haber al menos uno que se estableció en uno, y las implicaciones obligan a y a que se le asigne uno, y esto se reduce (estoy seguro de que esto se puede formalizar con inducción, aunque no he logrado ese nivel de detalle todavía). Tenga en cuenta que una asignación satsifying que sea óptima en el número de asignadas no se establecerá$N_i$$N$$N$$P_{ij}$$N_i$$N_j$$P_{ij}$ verdadero para dos pares y , por la razón de que las variables vienen con el equipaje adicional de las implicaciones, y las variables no (son allí para garantizar la satisfacción de EVEN-3: en una cláusula donde es verdadero y no es cierto, aún necesitamos elegir algo para satisfacer esa cláusula, y por razones que son fáciles de ver, esta no puede ser una variable universal a través de cláusulas).$(r,s)$$(r',s')$$P$$Q$$N_i$$P_{ij}$

Entonces, creo que una cadena de suma corresponde a una tarea satisfactoria y viceversa. Permítanme describir una parte de esto de manera formal: dada una cadena de suma, construimos una asignación que es satisfactoria. Para comenzar, establece todos los que se encuentran en la cadena en uno, y los otros en cero. Además, si aparece en la cadena de adición, entonces para cada , dejemos que sean los elementos en la cadena de modo que . Entonces establece en uno (y en cero), y todos modo que$f$$f$$N_i$$N_i$$k$$N_k$$i_k,j_k$$i_k + j_k = j$$f$$P_{i_k j_k}$$Q_{i_k j_k}$$(i,j)$$i \neq i_k$ y e , establece en uno (y en cero). Para todos los que no figuran en la cadena de suma, para todos manera que , establezca todos y en cero (observe que la coherencia se deriva del hecho de que dos números sumar de una sola manera). Cada cláusula que involucra un en la cadena se cumple porque una variable P o una variable Q correspondiente a ella se estableció en una (y observe que exactamente una de ellas está configurada en uno para cualquier par$j \neq j_k$$i+j = k$$f$$Q_{ij}$$P_{ij}$$k$$i,j$Q i j P i j N i ( i , j $i+j = k$$Q_{ij}$$P_{ij}$$N_i$$(i,j)$) Para cualquier otra cláusula, todo se establece en cero. Que las implicaciones se mantengan es fácil de verificar.

La parte que no está clara es la siguiente: porque para cada elemento elegido en la cadena de suma, la asignación incurre en un peso de (debido a que todas las variables se establecen en una). Por lo tanto, existe la posibilidad de que una cadena adicional más larga corresponda a una asignación más barata, pero estoy bastante seguro de que esto no sucede debido a una prueba en las siguientes líneas: considere una cadena de adición óptima y suponga que hay una más larga que tiene una asignación satisfactoria de menor peso que le corresponde. Claramente, los elementos de la cadena más larga excluyen al menos uno de la más corta; deje que ese elemento sea . Deseo decir que el costo incurrido cont Q x $t$$t$$Q$$x$$x$se incurre en la cadena más larga de todos modos, y el resto se compara favorablemente. Sin embargo, tengo que escribir esto cuidadosamente, ¡y podría estar viendo cosas del síndrome posterior a la medianoche!