Comment est difficile de démêler une chaîne?

Un mélange de deux chaînes est formé en intercalant les caractères dans une nouvelle chaîne, en maintenant les caractères de chaque chaîne dans l'ordre. Par exemple, MISSISSIPPIest un mélange de MISIPPet SSISI. Permettez-moi d'appeler un carré de corde s'il s'agit d'un mélange de deux chaînes identiques. Par exemple, ABCABDCDest carré, car c'est un mélange de ABCDet ABCD, mais la chaîne ABCDDCBAn'est pas carrée.

Existe-t-il un algorithme rapide permettant de déterminer si une chaîne est carrée ou est-ce NP-difficile? L'approche de programmation dynamique évidente ne semble pas fonctionner.

Même les cas spéciaux suivants semblent difficiles: (1) des chaînes dans lesquelles chaque caractère apparaît au maximum quatre fois sur six , et (2) des chaînes avec seulement deux caractères distincts. Comme Per Austrin le souligne ci-dessous, le cas particulier où chaque caractère apparaît au plus quatre fois peut être réduit à 2SAT.

---

Mise à jour: Ce problème a une autre formulation qui peut rendre une preuve de dureté plus facile.

Considérons un graphe G dont les sommets sont les entiers 1 à n; identifier chaque bord avec l'intervalle réel entre ses extrémités. Nous disons que deux arêtes de G sont imbriquées si un intervalle contient correctement l'autre. Par exemple, les arêtes (1,5) et (2,3) sont imbriquées, mais (1,3) et (5,6) ne le sont pas et (1,5) et (2,8) ne le sont pas. Une correspondance dans G est non imbriquée si aucune paire d'arêtes n'est imbriquée. Existe-t-il un algorithme rapide pour déterminer si G a une correspondance parfaite non imbriquée ou si ce problème est NP-difficile?

• Supprimer une chaîne équivaut à rechercher une correspondance parfaite non imbriquée dans une union disjointe de cliques (avec des bords entre des caractères égaux). En particulier, la suppression d'une chaîne binaire équivaut à la recherche d'une correspondance parfaite non imbriquée dans une union disjointe de deux cliques. Mais je ne sais même pas si ce problème est difficile pour les graphiques généraux, ou facile pour toute classe de graphiques intéressante.

• Il existe un algorithme polynomial facile à trouver non parfait passage appariements.

---

Mise à jour (24 juin 2013): le problème est résolu! Il existe maintenant deux preuves indépendantes indiquant que l'identification de chaînes carrées est NP-complète.

• En novembre 2012, Sam Buss et Michael Soltys ont annoncé une réduction du nombre de partitions 3 , ce qui montre que le problème est difficile, même pour les chaînes comportant un alphabet de 9 caractères. Voir "Un brassage de carrés, c'est NP-difficile ", Journal of Computer System Sciences 2014.

• En juin 2013, Romeo Rizzi et Stéphane Vialette ont publié une réduction du plus long problème de sous- séquence commun . Voir " Reconnaissance des mots qui sont des carrés pour le produit Shuffle ", Proc. 8ème Symposium international sur l'informatique en Russie , Springer LNCS 7913, p. 235–245.

Il existe également une preuve plus simple que trouver des correspondances parfaites non imbriquées est NP-difficile, en raison de Shuai Cheng Li et Ming Li en 2009. Voir " Deux problèmes non résolus de modèles à 2 intervalles ", Théorie de l'informatique 410 (24–25). ): 2410–2423, 2009.

Michael Soltys et moi avons réussi à prouver que le problème consistant à déterminer si une chaîne de caractères peut être écrite sous forme de mélange carré est NP complet. Ceci s'applique même sur un alphabet fini avec seulement symboles distincts, bien que notre preuve soit écrite pour un alphabet avec 9 symboles. Cette question reste ouverte pour les alphabets plus petits, par exemple avec seulement 2 symboles. Nous n’avons pas examiné le problème dans la mesure où chaque symbole n’apparaît que six fois (ou plus généralement un nombre de fois constant); donc cette question est toujours ouverte.$7$$9$$2$$6$

La preuve utilise une réduction de Partition. Il est trop long de poster ici, mais une pré-impression, "Le démêlage d'une chaîne est NP- dur", est disponible sur nos pages Web à l'adresse:$3$$\text{NP}$

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

et

http://www.cas.mcmaster.ca/~soltys/#Papers .

Le document a été publié dans le Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Dans le cas particulier que vous mentionnez lorsque chaque caractère apparaît au plus quatre fois, il y a une simple réduction à 2-SAT (sauf si quelque chose me manque ...), comme suit:

Le point crucial est que pour chaque personnage, il existe (au plus) deux manières valides de faire correspondre les occurrences du personnage (la troisième possibilité sera l’imbrication). Utilisez une variable booléenne pour représenter laquelle des deux correspondances est choisie. Maintenant, une affectation à ces variables donne un démêlage valide de la chaîne ssf pour chaque paire d'arêtes imbriquées, mais les deux n'ont pas été choisies. Cette condition peut être décrite avec précision par une disjonction des variables (éventuellement inversées) correspondant aux deux caractères impliqués.

Voici un algorithme qui a peut-être une chance d'être correct bien que cela semble difficile à prouver et je ne parierais pas la maison dessus ...

$G$$e$$G$$e$$e$

$G$$G$$G$$G$

$> 1$

Après le choix gourmand, nous purgeons à nouveau le graphique, etc., et le processus se termine lorsque le graphique est (espérons-le) une correspondance parfaite non imbriquée.

Au début, je pensais que cela ressemblait plus ou moins à une petite anticipation dans l’algorithme glouton et que cela ne fonctionnait pas vraiment, mais j’ai trouvé étonnamment difficile de trouver un contre-exemple.

La solution proposée par Sam Buss et moi-même en novembre 2012 (montrant que la suppression d'une case de NP-hard par une réduction de 3-Partition) est désormais un article publié dans le Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Romeo Rizzi et Stéphane Vialette prouvent que la reconnaissance des chaînes carrées est NP-complète dans leur document de 2013 intitulé " Reconnaître les mots qui sont des carrés pour le produit Shuffle ", en réduisant le plus long problème binaire de sous-séquence. Ils affirment que la complexité de la récupération des chaînes binaires est toujours ouverte.

Une preuve encore plus simple que la recherche de la correspondance parfaite non imbriquée est NP-complète est donnée par Shuai Cheng Li et Ming Li dans leur document de 2009 " Sur deux problèmes non résolus de modèles à 2 intervalles ". Cependant, ils utilisent une terminologie héritée de la bioinformatique. Au lieu de "correspondance parfaite non imbriquée", ils l'appellent le problème " DIS-2-IP- ". L'équivalence entre les deux problèmes est décrite par Blin, Fertin et Vialette :$\{<, \between\}$

Le problème 2-IP-DIS- a une formulation immédiate en termes de correspondances contraintes dans les graphes généraux: Soit un graphe associé à un ordre linéaire des sommets de , le 2-IP -DIS- est équivalent à trouver une cardinalité maximale correspondant à en avec la propriété qui, pour deux arêtes distinctes quelconques et de ni les et ni$\{<, \between\}$$G$$\pi$$G$$\{<, \between\}$$M$$G$$\{u, v\}$$\{u', v'\}$$M$$min \{ \pi(u), \pi(v) \} \lt min \{ \pi(u'), \pi(v') \}$$max \{ \pi(u'), \pi(v') \lt max \{ \pi(u), \pi(v) \}$$min \{ \pi(u'), \pi(v') \} \lt min \{ \pi(u), \pi(v) \}$ et se produisent.$max \{ \pi(u), \pi(v) \} \lt max \{ \pi(u'), \pi(v') \}$

Mise à jour (25 février 2019): Bulteau et Vialette ont montré que le problème de décision consistant à libérer une chaîne binaire est NP-complet dans leur document. Reconnaître les carrés de mélange binaires est NP-difficile .

est-ce que cela aide?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

N'OUBLIEZ JAMAIS, CETTE RÉPONSE EST FAUX. Il échoue à l'entrée "AABAAB": une correspondance avide des deux premiers A l'un avec l'autre rend impossible la correspondance des symboles restants. Je la laisse plutôt que de la supprimer pour aider les autres à ne pas commettre la même erreur.

Il me semble qu'il est toujours prudent d'associer chaque caractère successif du supposé carré à un autre personnage égal qui se trouve le plus tôt possible. C'est-à-dire que l'algorithme temporel linéaire suivant devrait fonctionner:

Boucle à travers chaque position i dans la chaîne d'entrée, i = 0, 1, 2, ... n. Pour chaque position i, vérifiez si cette position a déjà été comparée à une position antérieure de la chaîne. Si ce n'est pas le cas, comparez-le avec un caractère égal qui vient après la dernière position déjà appariée, sinon apparaît le plus tôt possible dans la chaîne. Si aucune correspondance n'est trouvée pour un caractère, déclarez que l'entrée n'est pas un carré; sinon, c'est l'ensemble des caractères de la première paire de chaque match.

La voici en Python:

def sqrt (S):
    allumettes = []
    i, j = 0, 0
    pendant que je <len (S):
        si j <len (correspond) et correspond à [j] [1] == i:
            i + = 1
            j + = 1
            Continuez
        si correspond:
            k = correspond à [-1] [1] + 1
        autre:
            k = 1
        tandis que k <len (S) et S [k]! = S [i]:
            k + = 1
        si k> = len (S):
            augmenter Exception ("Pas un carré")
        matches.append ((i, k))
        i + = 1
    retourne "" .join (S [a] pour a, b dans les correspondances)

print sqrt ("ABCABDCD")

Ici, i est la variable de boucle principale (la position que nous essayons de faire correspondre), j est un pointeur dans le tableau de paires appariées qui accélère la vérification de la correspondance de la position i et k est un index utilisé pour rechercher le caractère qui correspond à celui de la position i. C'est un temps linéaire car i, j et k augmentent de façon monotone à travers la chaîne et chaque itération de la boucle interne en augmente une.

Mise à jour: Il n’a aucun sens de parler de la difficulté de trouver une correspondance parfaite non imbriquée et non croisée, lorsque les étiquettes sont comprises entre 1 et n, car il n’en existe qu’une seule. (Oui, je me donne des coups de pied.) Cependant, cela aurait du sens étant donné une plus grande plage sur les étiquettes ... donc je vois encore un peu d'espoir, mais cela pourrait être assez inutile après tout. J'aurais certainement à en suivre un peu plus.

---

Je peux comprendre pourquoi il peut être difficile de trouver une correspondance non-imbriquée et non-croisée. Laissez-moi appeler une telle correspondance une correspondance disjointe . Je ne sais pas dans quelle mesure cela aide, mais permettez-moi de présenter le raisonnement de toute façon. (Je devrais souligner que mon argument, tel qu'il est rédigé ici, n'est pas complet et que les détails que je laisse de côté sont peut-être cruciaux. Cependant, j'imagine que cela pourrait être un début.)

Je vais commencer par un problème légèrement différent. Soit un graphe dont les arêtes sont colorées avec couleurs et dont les sommets sont étiquetés de à , existe-t-il une correspondance disjointe contenant exactement une arête de chaque couleur? Ce problème semble être NP-difficile (l'argument pour cela est à la fois complet et simple - à moins que je manque quelque chose). La réduction génère un graphique qui est une union disjointe de cliques.$G$$k$$1$$n$

La réduction provient de Disjoint Factors , un problème NP-complet introduit dans [1]. Un exemple de facteurs disjoints est donné par une chaîne sur un alphabet de taille , et la question est de savoir s'il existe facteurs disjoints, où un facteur est une sous-chaîne qui commence et se termine par la même lettre; et deux facteurs sont disjoints s'ils ne se chevauchent pas dans la chaîne (notez que l'imbrication, en particulier, est également interdite).$k$$k$

Permettez-moi de noter par , les éléments de l’ alphabet de taille associé à l’instance Disjoint Factors.$a_1,\ldots, a_k$$k$

Soit une instance de facteurs disjoints, c'est-à-dire une chaîne de longueur , créez un graphique comportant sommets avec des étiquettes de sommet de à . Ajoutez un bord entre les sommets et si les positions correspondantes ont la même lettre (disons ) et colorez également le bord avec la couleur .$n$$n$$1$$n$$u$$v$$a_i$$(u,v)$$i$

La preuve de la réduction découle essentiellement des définitions. Étant donné facteurs disjoints, nous avons clairement une correspondance colorée -disjoint, nous sélectionnons simplement les bords donnés par les facteurs disjoints, et il est facile de voir que la correspondance résultante est à la fois colorée et disjointe. A l' inverse, s'il y a un correspondant de -disjoint coloré, nous avons k facteurs disjoints, un pour chaque lettre, parce que la correspondance est colorée (et prend donc un facteur par lettre), et est disjointe (donc les facteurs correspondants ne se chevauchent pas )$k$$k$$k$

Pour supprimer les couleurs et faire en sorte que la correspondance soit parfaite, même sur une plage éventuellement plus large , apportez les modifications suivantes au graphique ainsi créé:

Soit le sous-ensemble de sommets dont les étiquettes sont des positions associées à la lettre . Si a des sommets , ajoutez nouveaux sommets et un graphe bipartite complet entre et les nouveaux sommets ajoutés. Répétez, bien sûr, pour chaque lettre. a U a A ( A - 2 ) U $U_a$$a$$U_a$$A$$(A-2)$$U_a$

En gros, si le graphe doit induire une correspondance parfaite, les sommets nouvellement introduits doivent correspondre aux sommets de , et ils tous sauf une paire de sommets et le bord entre les sommets restants correspondra au facteur disjoint. . Je n'ai pas encore déterminé les nombres que l'on doit associer aux sommets nouvellement ajoutés ... Notez qu'ils doivent l'être pour que la correspondance résultante soit disjointe. J'ai juste le sentiment (lire: espérons) que cela peut être fait!$U_a$

[1] Sur les problèmes sans noyaux polynomiaux , Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows et Danny Hermelin, J. Comput. Syst. Sci.

L'approche ne fonctionne pas: décomposer un carré mélangé en supprimant deux lettres correspondantes ne donne pas des carrés mélangés ... Voir les commentaires de Radu ci-dessous.

---

$\Sigma$

$${\small \begin{aligned} S(XY)&\Rightarrow A(X,Y)&(1)\newline A(aX_1, aX_2Y_1Y_2)&\Rightarrow A(X_1,Y_1)\,A(X_2,Y_2)&(2)\newline A(\varepsilon,\varepsilon)&\Rightarrow\varepsilon&(3) \end{aligned}}$$ $a$$\Sigma$$\varepsilon$

$X_1$$Y_1$$Y_1$$X_2$$Y_2$$Y_1$$Y_2$$X_1$$X_2$

$abcabdcd$

$${\small\begin{aligned} S(abcabdcd) &\Rightarrow A(abc, abdcd) &(\text{by } 1, X=abc, Y=abdcd)\newline &\Rightarrow A(bc,bdcd)\,A(\varepsilon,\varepsilon)&(\text{by } 2, X_1=bc, Y_1=bdcd, X_2=Y_2=\varepsilon)\newline &\Rightarrow A(c,c)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 3)\newline &\Rightarrow A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 3)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow^3\varepsilon&\text{i.e. success} \end{aligned}}$$

$0011$

$${\small\begin{aligned} S(0011)&\Rightarrow A(0,011)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(1,1)\newline &\Rightarrow A(1,1)\newline &\Rightarrow^\ast \varepsilon \end{aligned}}$$

$X$$Y$

Mise à jour: comme le souligne Tsuyoshi Ito dans les commentaires, cet algorithme a une durée d'exécution exponentielle.

Message original:

Voici comment je programmerais cela dans le monde réel.

On nous donne une chaîne S = (S [1], ..., S [n]). Pour chaque préfixe S_r = (S [1], ..., S [r]), il existe un ensemble {(T_i, U_i)} de paires de chaînes, tel que S_r est un mélange de (T_i, U_i), et T_i est un préfixe de U_i (c.-à-d. que U_i commence par «T_i). S_r est lui-même un carré si et seulement si cet ensemble contient une paire (T_i, U_i) avec T_i = U_i.

Maintenant, nous n'avons pas besoin de générer toutes ces paires; il suffit de générer le suffixe V_i de chaque chaîne U_i obtenue en supprimant sa copie de T_i. Cela éliminera un nombre (éventuellement exponentiel) de doublons non pertinents. Maintenant, S_r est un carré si et seulement si cet ensemble de suffixes contient la chaîne vide. Donc, l'algorithme devient:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

Par exemple, si S est AABAAB:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

Nous pouvons supprimer tous les suffixes qui sont plus de la moitié de la longueur de la chaîne d'entrée. Cela simplifie donc:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

J'ai programmé cela en C ++, et cela fonctionne sur tous les exemples donnés ici. Je peux poster le code, si quelqu'un est intéressé. La question est la suivante: la taille de SuffixSet peut-elle croître plus rapidement que polynomial?

EDIT: Ceci est une réponse incorrecte.

---

Sylvain a suggéré un GCR qui, malheureusement, n’était pas approprié pour ces "carrés de mélange". Cependant, je pense qu'il en existe un (EDIT: pas un GCR, voir les commentaires de Kurt ci-dessous!) , Qui se présente comme suit:

$\begin{aligned} S(Y) & \rightarrow A(\epsilon,Y) & (1) \newline A(X, ZY) & \rightarrow A(XZ,Y) & (2) \newline A(aX, aY) & \rightarrow A(X,Y) \quad \text{ for every } a \in \Sigma & (3) \newline A(\epsilon,\epsilon) & \rightarrow \epsilon & (4) \end{aligned}$

$a$$a'$$b$$b'$$a \prec b$$a' \prec b'$$\prec$$(1,2)$$(3)$$(2)$

$100110101010$

$\begin{aligned} S(100110101010) & \Rightarrow A(\epsilon,100110101010) & (1) \newline & \Rightarrow A(1001,10101010) & (2) \newline & \Rightarrow^* A(01,101010) & (3) \newline & \Rightarrow A(011,01010) & (2) \newline & \Rightarrow^* A(1,010) & (3) \newline & \Rightarrow A(10,10) & (2) \newline & \Rightarrow^* A(\epsilon, \epsilon) & (3) \newline & \Rightarrow \epsilon & (4) \end{aligned}$

Je n'ai pas élaboré de preuve formelle que cette grammaire capture bien les "carrés de mélange", mais cela ne devrait pas être trop difficile. Sylvain a déjà mentionné que le problème de décision pour les GCR est polynomial.