Est-il difficile de trouver des chaînes d'addition optimales?

Une chaîne d'addition est une séquence d'entiers positifs où et chaque index , nous avons pour certains indices . La longueur de la chaîne d'addition est ; la cible de la chaîne d'addition est .x 1 = 1 i ≥ 2 x i = x j + x k 1 ≤ j , k < i n x $(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$

Que sait-on de la complexité du problème suivant: étant donné un entier , quelle est la longueur de la chaîne d'addition la plus courte dont la cible est ? Est-ce NP-difficile?$N$$N$

Wikipedia pointe vers un article de Downey, Leong et Sethi de 1981 qui prouve que le problème connexe suivant est NP-difficile: étant donné un ensemble d'entiers, quelle est la longueur minimale d'une chaîne d'addition qui comprend l'ensemble entier? Plusieurs auteurs affirment apparemment que ce document prouve que le problème à cible unique est NP-difficile, mais ce n'est pas le cas.

Le problème est mentionné comme étant ouvert dans la thèse de doctorat d'Eric Lehman "Algorithmes d'approximation pour la compression de données basée sur la grammaire" en 2002. D'après la p35 de la thèse:

"Néanmoins, une solution exacte au problème de la chaîne d'addition reste étrangement insaisissable. La méthode M-ary s'exécute dans le polylogue temporel (n) et donne une approximation 1 + o (1). Cependant, même si exponentiellement plus de temps est autorisé, poly ( n), aucun algorithme exact n'est connu. "

Et sur le papier principal de la thèse de Lehman, il y a un bon aperçu du problème (section VB) avec des références.

Je voudrais documenter certains progrès partiels - apparemment prometteurs jusqu'à présent - vers un algorithme de temps polynomial. MISE À JOUR : Ajout de quelques détails pour tenir compte d'un problème signalé par @David (merci!).

L'approche consiste à réduire cela à une instance de MIN-ONES EVEN-3 CSP (MOEC), qui se trouve être un problème résolvable en temps polynomial. La preuve de la réduction est un peu floue, mais j'espère qu'elle existe!

Une instance de MOEC est une famille de sous-ensembles à dimensions d'un univers de variables et un entier k . La question est de savoir s'il existe une affectation satisfaisante de poids au plus k , où une affectation est une fonction de l'univers à { 0 , 1 } , le poids d'une affectation est le nombre de variables qu'il attribue à une, et une affectation est vérifiant si, pour chaque sous-ensemble de variables { x , y , z } , l'affectation (disons f ) a la propriété que:$3$$k$$k$$\{0,1\}$$\{x,y,z\}$$f$

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

Vous pouvez visualiser ceci comme 3-SAT avec une notion différente de satisfiabilité - choisissez aucun ou choisissez deux. Je serai un peu laxiste à propos de l'instance de MOEC dans la mesure où je permettrai, en dehors des sous-ensembles habituels , des implications, des disjonctions de longueur deux et de la contrainte ( x = 1 ) . Je crois que ces ajouts simples garderont le temps polynomial du problème.$3$$(x = 1)$

Disons que nous réduisons le problème de la chaîne d'addition pour le nombre . La variable définie pour cette réduction est la suivante:$n$

Pour chaque , la variable N i . Je récrire la variable N n comme N . Pour chaque paire i , j telle que 1 ≤ i , j ≤ k , introduisez les variables P i j et Q i j . $1 \leq i \leq n$$N_i$$N_n$$N$$i,j$$1 \leq i,j \leq k$$P_{ij}$$Q_{ij}$

Introduisez les sous-ensembles suivants, pour tout tels que k = i + j :$i,j,k$$k = i+j$

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

et les implications suivantes:

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

et les contraintes suivantes:

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

Enfin, nous devons ajouter des contraintes qui garantissent qu'au moins une des variables est choisie lorsqu'une variable N "correspondante" (pardonnez l'abus de notation) en est affectée une. Cela peut être fait en ajoutant la contrainte OR habituelle sur tout P i j telle que i + j soit la somme de la variable N en question. Nous devons cependant trouver un moyen de ré-encoder cela dans le cadre MOEC.$P$$N$$P_{ij}$$i + j$$N$

Permettez-moi donc de décrire une façon générale de dire, étant donné un ensemble de variables:

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

comment la contrainte "si une affectation est satisfaisante et met à un, alors exactement l'un des l i doit être mis à un par l'affectation", peut être codée avec la syntaxe MOEC. Notez que cela suffit pour nos besoins, nous introduisons simplement les contraintes:$X$$l_i$

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

L'encodage se fait comme suit. Soit l'arbre binaire complet enraciné sur t feuilles. Introduisez une nouvelle variable T d i pour tout 1 ≤ d ≤ log t et 1 ≤ i ≤ L ( d ) , où L ( d ) représente le nombre de nœuds de T X à la profondeur d .$T_X$$t$$T_{di}$$1 \leq d \leq \log t$$1 \leq i \leq {\cal L}(d)$${\cal L}(d)$$T_X$$d$

Pour chaque nœud , si p et q sont ses enfants dans l'arbre, introduisez la contrainte EVEN-3:$T_{di}$$p$$q$

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

Cela signifie que si une variable correspondant à un nœud est définie sur true, alors exactement l'un de ses enfants doit également être défini sur true. Ajoutez maintenant les implications:

et ( d log t , j ) ⇒ l j (virgule pour plus de clarté).$(X \Rightarrow T_{11})$$(d_{\log t,j}) \Rightarrow l_j$

Cette combinaison de contraintes et d'implications EVEN-3 équivaut à une contrainte que nous souhaitions encoder.

Intuitivement, ce qui se passe, c'est que les deux dernières contraintes déclenchent exactement les réactions requises pour construire une chaîne d'addition. En particulier, penchons-nous sur les qui leur sont attribués par une affectation satisfaisante - la revendication est qu'ils formeront une chaîne d'addition pour N : puisque l'affectation est forcée de mettre N à un, il doit y avoir au moins un P i j qui a été fixé à un, et les implications forcent N i et N $N_i$$N$$N$$P_{ij}$$N_i$$N_j$à en attribuer un, et cela va jusqu'au bout (je suis sûr que cela peut être officialisé par l'induction, même si je n'ai pas encore défini ce niveau de détail). Notez qu'une affectation satsifiante qui est optimale dans le nombre de celles attribuées ne mettra pas vrai pour deux paires ( r , s ) et ( r ′ , s ′ ) , pour la raison que les variables P viennent avec les variables supplémentaires bagage des implications, et les variables Q ne le font pas (elles sont là pour assurer la satisfiabilité EVEN-3 - sur une clause où N i est vrai et $P_{ij}$$(r,s)$$(r',s')$$P$$Q$$N_i$ n'est pas vrai, nous devons encore choisir quelque chose pour satisfaire cette clause, et pour des raisons qui sont faciles à voir, cela ne peut pas être une variable universelle entre les clauses).$P_{ij}$

Je pense donc qu'une chaîne d'addition correspond à une affectation satisfaisante et vice-versa. Permettez-moi de décrire une partie de cela de manière quelque peu formelle: étant donné une chaîne d'addition, nous construisons une affectation qui est satisfaisante. Pour commencer, f met à 1 tous les N i qui figurent dans la chaîne et les autres N i à zéro. De plus, si k figure dans la chaîne d'addition, alors pour chaque N k , soit i k , j k les éléments de la chaîne tels que i k + j k = j . Alors f définit$f$$f$$N_i$$N_i$$k$$N_k$$i_k,j_k$$i_k + j_k = j$$f$ à un (et Q i k j k à zéro), et tous ( i , j ) tels que i ≠ i k et j ≠ j k et i + j = k , f fixe Q i j à un (et P i j à zéro). Pour tout k qui ne figure pas dans la chaîne d'addition, pour tout i , j tel que$P_{i_k j_k}$$Q_{i_k j_k}$$(i,j)$$i \neq i_k$$j \neq j_k$$i+j = k$$f$$Q_{ij}$$P_{ij}$$k$$i,j$ , mettez tous les Q i j et P i j à zéro (notez que la cohérence découle du fait que deux nombres s'additionnent d'une seule manière). Chaque clause impliquant un N i dans la chaîne est satisfaite car une variable P ou une variable Q correspondant à celle-ci a été définie sur un (et notez que l'un d'entre eux est défini sur un pour n'importe quelle paire ( i , j ) ). Pour chaque autre clause, tout est mis à zéro. Il est facile de vérifier les implications.$i+j = k$$Q_{ij}$$P_{ij}$$N_i$$(i,j)$

La partie qui n'est pas claire est la suivante: parce que pour chaque élément choisi dans la chaîne d'addition, l'affectation encourt un poids de t (car toutes les variables Q sont définies sur un). Il est donc possible qu'une chaîne supplémentaire plus longue corresponde à une affectation moins chère, mais je suis sûr que cela ne se produit pas en raison d'une preuve dans le sens suivant: considérez une chaîne d'addition optimale et supposez qu'il y en a une plus longue qui a une affectation satisfaisante de moindre poids qui lui correspond. De toute évidence, les éléments de la chaîne la plus longue en excluent au moins un de la plus courte - que cet élément soit x . Je tiens à dire que le coût encouru avec $t$$t$$Q$$x$$x$est engagé de toute façon dans la chaîne la plus longue, et le reste se compare favorablement. Cependant, je dois l'écrire attentivement, et je pourrais juste voir des choses du syndrome post-minuit!