¿Qué tan difícil es arrastrar una cuerda?

117

Se forma una mezcla de dos cadenas intercalando los caracteres en una nueva cadena, manteniendo los caracteres de cada cadena en orden. Por ejemplo, MISSISSIPPIes una combinación de MISIPPy SSISI. Permítanme llamar a un cuadrado de cadena si es una combinación de dos cadenas idénticas. Por ejemplo, ABCABDCDes cuadrado, porque es una combinación de ABCDy ABCD, pero la cadena ABCDDCBAno es cuadrada.

¿Existe un algoritmo rápido para determinar si una cadena es cuadrada o es NP-hard? El obvio enfoque de programación dinámica no parece funcionar.

Incluso los siguientes casos especiales parecen ser difíciles: (1) cadenas en las que cada carácter aparece como máximo cuatro seis veces, y (2) cadenas con solo dos caracteres distintos. Como señala Per Austrin a continuación, el caso especial en el que cada personaje aparece como máximo cuatro veces se puede reducir a 2SAT.


Actualización: este problema tiene otra formulación que puede facilitar la prueba de dureza.

Considere una gráfica G cuyos vértices son los enteros 1 a n; identifique cada borde con el intervalo real entre sus puntos finales. Decimos que dos bordes de G están anidados si un intervalo contiene adecuadamente el otro. Por ejemplo, los bordes (1,5) y (2,3) están anidados, pero (1,3) y (5,6) no lo están, y (1,5) y (2,8) no lo están. Una coincidencia en G no está anidada si no hay ningún par de aristas anidado. ¿Existe un algoritmo rápido para determinar si G tiene una coincidencia perfecta no anidada, o ese problema es NP-difícil?

  • Desarmar una cadena es equivalente a encontrar una coincidencia perfecta no anidada en una unión disjunta de camarillas (con bordes entre caracteres iguales). En particular, deshacer una cadena binaria es equivalente a encontrar una coincidencia perfecta no anidada en una unión disjunta de dos camarillas. Pero ni siquiera sé si este problema es difícil para los gráficos generales, o fácil para cualquier clase interesante de gráficos.

  • Existe un algoritmo de tiempo polinómico fácil para encontrar coincidencias perfectas sin cruzamiento .


Actualización (24 de junio de 2013): ¡El problema está resuelto! Ahora hay dos pruebas independientes de que identificar cadenas cuadradas es NP-complete.

También hay una prueba más simple de que encontrar coincidencias perfectas no anidadas es NP-difícil, debido a Shuai Cheng Li y Ming Li en 2009. Ver " Sobre dos problemas abiertos de patrones de 2 intervalos ", Theoretical Computer Science 410 (24–25 ): 2410–2423, 2009.

Jeffε
fuente
2
¿No es la secuencia solo A000984, el "número de valores posibles de un número binario de 2 * n bits para el cual la mitad de los bits están activados y la otra mitad están desactivados"?
Travis Brown el
55
@Travis, a menos que esté malentendido: para n = 4, 10000111 es un número binario de 2 * n bits para el cual la mitad de los bits están activados y la otra mitad, pero que no es un cuadrado, como se define. Siguiendo esa lógica, dado que los cuadrados son un subconjunto estricto del conjunto que genera A000984, los valores de los cuadrados sobre un alfabeto binario deberían ser menores en índices iguales a través de la secuencia, ¿no?
Daniel Apon
1
Observación: Usando el formalismo gráfico, que 2n sea el número de vértices en G. Sea G 'un gráfico obtenido de la gráfica lineal de G al sumar los bordes entre los vértices correspondientes a los bordes anidados de G. El problema pregunta si G' tiene Un conjunto independiente de tamaño n. Existen varias clases de gráficos en los que se puede calcular un conjunto polinomial máximo independiente. Si seguimos esta ruta, la pregunta es: ¿Qué buenas propiedades tiene G '? (más)
Tsuyoshi Ito
2
@Radu: No creo que la fracción de cuadrados a no cuadrados (sobre alfabetos binarios) converja a 1/3. Hice algunas simulaciones de Montecarlo que indican una convergencia lenta a 1/2. Por lo tanto, en el límite, esencialmente todas las cadenas binarias con números pares de 0 y 1 son cuadrados. Esto es sorprendente para mí, y puede ser explotable en un algoritmo. Para alfabetos más grandes, la fracción de cuadrados parece converger rápidamente a 0.
Martin Berger
8
Como esta pregunta se menciona en la publicación del blog de hoy, veamos si podemos obtener un renovado interés en resolver este problema. Ha pasado un año desde que se planteó esta pregunta, y hemos ganado muchos nuevos usuarios desde entonces. He puesto una recompensa de 100 repeticiones por la pregunta.
Alex ten Brink

Respuestas:

66

Michael Soltys y yo hemos logrado demostrar que el problema de determinar si una cadena se puede escribir como una combinación aleatoria es NP completo. Esto se aplica incluso sobre un alfabeto finito con solo símbolos distintos, aunque nuestra prueba está escrita para un alfabeto con símbolos. Esta pregunta aún está abierta para alfabetos más pequeños, digamos con solo símbolos. No hemos analizado el problema bajo la restricción de que cada símbolo aparece solo veces (o, más generalmente, un número constante de veces); entonces esa pregunta aún está abierta.9 2 67926

La prueba utiliza una reducción de Partición. Es demasiado largo para publicar aquí, pero hay una preimpresión, "Desorganizar una cadena es -hard", está disponible en nuestras páginas web en:NP3NP

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

y

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

El artículo ha sido publicado en el Journal of Computer System Sciences:

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

Sam Buss
fuente
11
¡¡Increíble!! (Y para mi inmenso alivio, seriamente no trivial.)
Jeff el
15
Gracias. StackExchange fue nuestra fuente para esta pregunta. ¡Es un gran recurso!
Sam Buss
99
@SamBuss una pequeña solicitud: mientras cita la pregunta de Jeff, solo menciona la solución de Per Austrin en el texto. Si observa las respuestas, también hay una manera de generar una cita formal para las respuestas (haga clic en el botón compartir y presione el enlace 'citar'). De esa manera, también puede generar una cita adecuada para la respuesta de Per. Solo menciono esto para que las personas que hacen contribuciones formales en el sitio también puedan obtener un reconocimiento formal. Gracias ! y felicidades por resolver este problema
Suresh Venkat
2
@SureshVenkat. Gracias por el consejo: esto es útil. He agregado esto a la versión en línea del documento.
Sam Buss el
El problema de reconocer un shuffle cuadrado ahora ha demostrado ser difícil incluso en un alfabeto binario: sciencedirect.com/science/article/pii/S0304397519300258
a3nm
58

Para el caso especial que mencionas cuando cada personaje aparece como máximo cuatro veces, hay una reducción simple a 2-SAT (a menos que me falte algo ...), de la siguiente manera:

El punto crucial es que para cada personaje, hay (como máximo) dos formas válidas de hacer coincidir las apariciones del personaje (la tercera posibilidad será anidar). Use una variable booleana para representar cuál de las dos coincidencias se elige. Ahora, una asignación a estas variables proporciona una combinación aleatoria válida de la cadena iff para cada par de bordes anidados, no se eligieron ambos. Esta condición puede describirse con precisión mediante una disyunción de las variables (posiblemente negadas) correspondientes a los dos caracteres involucrados.

Por Austrin
fuente
Agradable. La misma idea se generaliza a las cadenas donde cada personaje aparece como máximo seis veces, pero el resultado es una instancia de 5-SAT. :-(
Jeffε
2
Esta respuesta es la favorita para ganar la recompensa.
Jeffε
así que esto parece demostrar que el problema es NPC y por qué necesitamos pruebas largas de conferencias y diarios.
T ....
@Turbo Mucho retraso, pero esto no prueba que el problema sea NPC porque 2-SAT no es NPC; está en P.
Steven Stadnicki
¿Funciona esta reducción a 2-SAT si el tamaño del alfabeto no tiene límites?
Mohammad Al-Turkistany
11

Aquí hay un algoritmo que puede tener alguna posibilidad de ser correcto, aunque parece difícil de probar y no apostaría la casa por eso ...

GeGee

GGGG

>1

Después de la elección codiciosa, purgamos el gráfico nuevamente, y así sucesivamente, y el proceso termina cuando el gráfico es (con suerte) una coincidencia perfecta que no se anida.

Al principio pensé que esto sería más o menos como tener una pequeña mirada hacia adelante en el algoritmo codicioso y no funcionar realmente, pero me pareció sorprendentemente difícil encontrar un contraejemplo.

Por Austrin
fuente
Soy escéptico sobre la segunda fase codiciosa, pero parece útil purgar el gráfico. En el contexto de cadena original, donde el gráfico es la unión disjunta de camarillas, ¿puede decir algo sobre la estructura del gráfico purgado? ¿Sigue siendo una unión disjunta de camarillas? (En otras palabras, ¿puede dividir las apariciones de cada carácter en la cadena de entrada para que los caracteres en diferentes partes no puedan coincidir?)
Jeffε
2
Para la segunda pregunta, considere la cadena 'aaaa'. Purgarlo elimina los bordes 1-4 y 2-3, dando un ciclo de 4. Dos variaciones del segundo paso codicioso que también serían suficientes y que no podría encontrar ningún contraejemplo son: 1) Un gráfico purgado tiene una coincidencia perfecta no anidada si tiene una coincidencia perfecta (esto parece incomparable al paso codicioso) . 2) En una gráfica se purgó con una correspondencia perfecta no anidación, cada borde se utiliza en algunos correspondencia perfecta no anidación (esto es más fuerte que tanto el paso codicioso y el primer elemento por lo que debe ser más fácil de refutar).
Por Austrin
11

La solución que Sam Buss y yo propusimos en noviembre de 2012 (que muestra que quitar un cuadrado en NP-hard por una reducción de 3-Partition) ahora es un artículo publicado en el Journal of Computer System Sciences:

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

Michael Soltys
fuente
2
Esto realmente debería ser una edición de la respuesta anterior de Sam Buss, en lugar de una respuesta separada. Puede hacer clic en "editar" para sugerir una edición a la respuesta de otra persona, y su edición será revisada por otros usuarios del sitio.
DW
11

Romeo Rizzi y Stéphane Vialette demuestran que el reconocimiento de cadenas cuadradas es NP-complete en su artículo de 2013 " Sobre el reconocimiento de palabras que son cuadrados para el producto aleatorio ", por reducción del problema de subsecuencia binaria más largo. Afirman que la complejidad de mezclar cadenas binarias aún está abierta.

Shuai Cheng Li y Ming Li dan una prueba aún más simple de que encontrar una coincidencia perfecta no anidada es NP-complete en su artículo de 2009 " Sobre dos problemas abiertos de patrones de 2 intervalos ". Sin embargo, usan terminología heredada de bioinformática. En lugar de "coincidencia no anidada perfecta", lo llaman el "problema DIS-2-IP- ". Blin, Fertin y Vialette describen la equivalencia entre los dos problemas :{<,}

El problema 2-IP-DIS- tiene una formulación inmediata en términos de coincidencias restringidas en gráficos generales: dado un gráfico junto con un ordenamiento lineal de los vértices de , el 2-IP -DIS- problema es equivalente a encontrar una cardinalidad máxima que coincida con en con la propiedad de que para dos bordes distintos y de ni y ni{<,}GπG{<,}MG{u,v}{u,v}Mmin{π(u),π(v)}<min{π(u),π(v)}max{π(u),π(v)<max{π(u),π(v)}min{π(u),π(v)}<min{π(u),π(v)} y ocurren.max{π(u),π(v)}<max{π(u),π(v)}

Actualización (25 de febrero de 2019): Bulteau y Vialette demostraron que el problema de decisión de desarmar una cadena binaria es NP completo en su trabajo, Reconocer los cuadrados aleatorios binarios es NP-duro .

Mohammad Al-Turkistany
fuente
No veo la conexión, y no veo dónde los autores afirman que quitar una cadena es equivalente a su problema.
Suresh Venkat
2
No dicen que es equivalente a desarmar; Es un problema más general.
Jeffε
@SureshVenkat Edité mi respuesta, espero que sea más clara. Básicamente, lo que dicen en la nota al pie es que cualquiera de los dos bordes en la coincidencia ( ) no están anidados. M
Mohammad Al-Turkistany
En la versión real publicada, la equivalencia se indica en la página 320. books.google.com/…
Mohammad Al-Turkistany
Editado para enterrar el lede .
Jeffε
9

¿Esto ayuda?

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

Aaron Sterling
fuente
77
Buena referencia Es difícil ver cómo los resultados se aplicarían a mi problema, pero tal vez las técnicas ayudarían. Es fácil saber si una cadena X dada es una combinación de dos copias de otra cadena Y. El documento adjunto demuestra que es NP difícil decidir si una cadena X determinada es una combinación de cualquier número de copias de otra cadena Y. Quiero saber si una cadena X dada es una mezcla de dos copias de
ALGUNA
5

NUNCA MENTE, ESTA RESPUESTA ES INCORRECTA. Falla en la entrada "AABAAB": hacer coincidir con avidez las dos primeras A entre sí hace que sea imposible hacer coincidir los símbolos restantes. Lo dejo en lugar de eliminarlo para ayudar a otros a evitar cometer el mismo error.

Me parece que siempre es seguro hacer coincidir con avidez cada personaje sucesivo del supuesto cuadrado con otro personaje igual que esté en la posición más temprana posible. Es decir, creo que el siguiente algoritmo de tiempo lineal debería funcionar:

Recorre cada posición i en la cadena de entrada, i = 0, 1, 2, ... n. Para cada posición i, verifique si esa posición ya se ha comparado con alguna posición anterior en la cadena. Si no, combínelo con un carácter igual que viene después de la última posición ya coincidente y, de lo contrario, es lo más temprano posible en la cadena. Si no se encuentra una coincidencia para algún carácter, declare que la entrada no es un cuadrado; de lo contrario, es el conjunto de caracteres en el primer par de cada partida.

Aquí está en Python:

def sqrt (S):
    coincidencias = []
    i, j = 0, 0
    mientras yo <len (S):
        si j <len (coincide) y coincide [j] [1] == i:
            i + = 1
            j + = 1
            Hacer continuación
        si coincide:
            k = coincide [-1] [1] + 1
        más:
            k = 1
        mientras que k <len (S) y S [k]! = S [i]:
            k + = 1
        si k> = len (S):
            elevar Excepción ("No es un cuadrado")
        partidos.append ((i, k))
        i + = 1
    return "" .join (S [a] para a, b en partidos)

print sqrt ("ABCABDCD")

Aquí i es la variable del bucle principal (la posición que estamos tratando de hacer coincidir), j es un puntero en la matriz de pares coincidentes que acelera la comprobación de si la posición i ya coincide, yk es un índice utilizado para buscar El personaje que coincide con el de la posición i. Es tiempo lineal porque i, j y k aumentan monotónicamente a través de la cadena y cada iteración del bucle interno aumenta uno de ellos.

David Eppstein
fuente
44
Estado allí. Hecho eso :-)
Jeffε
5

Actualización: No tiene sentido hablar de la dificultad de encontrar perfecta coincidencia que no es de anidación y no cruce, cuando las etiquetas son de 1 a n, porque sólo hay uno de ellos. (Sí, me estoy pateando). Sin embargo, tendría sentido dado un rango más amplio en las etiquetas ... así que todavía veo algo de esperanza, pero después de todo podría ser bastante inútil. Sin duda tendría que seguir con esto un poco más.


No puedo pensar en por qué podría ser difícil encontrar un juego que no es de anidación y no cruce. Permítanme llamar a tal coincidencia una coincidencia disjunta . No estoy seguro de hasta qué punto esto ayuda, pero permítanme presentar el razonamiento de todos modos. (Debo señalar que mi argumento, tal como está aquí, no está completo, y el detalle que dejo de lado es posiblemente crucial. Sin embargo, imagino que podría ser algo así como un comienzo).

Comenzaré con un problema ligeramente diferente. Dado un gráfico cuyos bordes están coloreados con colores y los vértices están etiquetados de a , ¿hay una coincidencia disjunta que contenga exactamente un borde de cada color? Este problema parece ser NP-hard (el argumento para esto es completo y directo, a menos que me falte algo). La reducción arroja un gráfico que es una unión disjunta de camarillas.k 1 nGk1n

La reducción es de Factores Disjuntos , un problema NP-completo introducido en [1]. Una secuencia de factores disjuntos es dada por una cadena sobre un alfabeto de tamaño , y la pregunta es si hay factores disjuntos, donde un factor es una subcadena que comienza y termina con la misma letra; y dos factores son disjuntos si no se superponen en la cadena (tenga en cuenta que 'anidar', en particular, también está prohibido).kkk

Permítanme denotar por , los elementos del alfabeto de tamaño asociados con la instancia de Factores disjuntos. ka1,,akk

Dada una instancia de factores disjuntos, es decir, digamos una cadena de longitud , cree un gráfico que tenga vértices con etiquetas de vértice de a . Agregue un borde entre los vértices y si las posiciones correspondientes tienen la misma letra (digamos ), y también colorea el borde con el color .n 1 n unn1nua i ( u , v ) ivai(u,v)i

La prueba de la reducción se deriva esencialmente de las definiciones. Dados los factores disjuntos, claramente tenemos una coincidencia de colores disjuntos, simplemente escogemos los bordes según los factores disjuntos, y es fácil ver que la coincidencia resultante es colorida y disjunta. Por el contrario, si hay un colorido juego -disjoint, entonces tenemos k factores disjuntos, uno para cada letra, porque el juego es colorido (y por lo tanto recoge uno de los factores por letra), y es disjunta (por lo que los factores correspondientes no se superpondrán )k kkkk

Para deshacerse de los colores y hacer que la combinación sea perfecta, aunque en un rango posiblemente mayor , realice las siguientes modificaciones en el gráfico así creado:

Deje que denote el subconjunto de vértices que tienen etiquetas que son posiciones asociadas con la letra . Si tiene vértices , entonces agregue nuevos vértices e induzca un gráfico bipartito completo entre y los vértices recién agregados. Repita, por supuesto, para cada letra. a U a A ( A - 2 ) U aUaaUaA(A2)Ua

Hablando en términos generales, si el gráfico debe inducir una coincidencia perfecta, los vértices recién introducidos deben coincidir con los vértices de , y todos menos un par de vértices, y el borde entre los vértices restantes corresponderá al factor disjunto . No he resuelto los números que uno debe asociar con los vértices recién agregados ... tenga en cuenta que deben ser para que la coincidencia resultante sea disjunta. ¡Solo tengo la sensación (léase: esperanza) de que 'se puede hacer'!Ua

[1] Sobre problemas sin núcleos polinomiales , Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows y Danny Hermelin, J. Comput. Syst. Sci.

Neeldhara
fuente
3
Estoy confundido. ¿No es (1,2), (3,4), (5,6), ..., (n-1, n) la ÚNICA combinación disjunta perfecta?
Jeff el
Una vez que me muevo al escenario de 'coincidencia perfecta', modifico la construcción y agrego muchos vértices nuevos (tenga en cuenta que agrego | U_a | -2 nuevos vértices por cada a en el alfabeto). Por lo tanto, n explotará en consecuencia, aproximadamente a 2n-2k, para un alfabeto de tamaño k. Espero haber dejado en claro que la reducción es incompleta ya que no he especificado qué números se asignan a los nuevos vértices, pero tengo la esperanza de que se pueda extender sin demasiada dificultad. Sin embargo, ciertamente tengo que pensarlo un poco antes de poder decir algo más.
Neeldhara
1
Creo que el punto del comentario de JeffE es que es fácil encontrar una coincidencia perfecta que no anide y no cruce (o informe la ausencia de la misma) porque solo hay una posibilidad.
Tsuyoshi Ito
2
No estoy hablando del contenido de su idea de prueba, pero estoy hablando de la primera oración de su respuesta: "Puedo pensar por qué podría ser difícil encontrar una coincidencia perfecta que no anide y no cruce". Esta tarea es fácil por la razón que escribió JeffE.
Tsuyoshi Ito
2
Sin la restricción de coloración impuesta por el problema del factor disjunto (como máximo un borde de cada color), también es fácil encontrar coincidencias disjuntas máximas.
Jeffε
1

El enfoque no funciona: descomponer un cuadrado barajado sacando dos letras coincidentes no da como resultado cuadrados barajados ... Ver los comentarios de Radu a continuación.


Una propuesta de uso de la gama de concatenación Gramáticas (RCGS, ver http://hal.inria.fr/inria-00073347/en/ ): I 'm estaba bajo la impresión de que el siguiente RCG sencilla reconoce su 'arrastrando los pies cuadrados' lenguaje durante un finita alfabeto , EDITADO después del primer comentario de Radu: donde rango sobre y denota el vacío cuerda.S ( X Y )Σ

S(XY)A(X,Y)(1)A(aX1,aX2Y1Y2)A(X1,Y1)A(X2,Y2)(2)A(ε,ε)ε(3)
aΣε

La gramática verifica con el segundo predicado que coincide con una letra de la aparición de la primera palabra con la misma letra en la aparición de la segunda palabra. Luego adivina cómo hacer coincidir el resto de las letras de la primera palabra restante, es decir, con una subcadena del resto, es decir, . tanto, todo antes de pertenece a la primera instancia de palabra; Lo llamamos y suponemos que coincide con algún sufijo que comienza en . Tenga en cuenta que e pueden contener letras de ambas instancias de la palabra, pero y solo contienen letras de la primera instancia.X1Y1Y1X2Y2Y1Y2X1X2

Por ejemplo, aquí hay una posible derivación de su cadena : abcabdcd

S(abcabdcd)A(abc,abdcd)(by 1,X=abc,Y=abdcd)A(bc,bdcd)A(ε,ε)(by 2,X1=bc,Y1=bdcd,X2=Y2=ε)A(c,c)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(ε,ε)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(d,d)A(ε,ε)(by 3)A(d,d)A(ε,ε)(by 3)A(ε,ε)A(ε,ε)A(ε,ε)(by 2)3εi.e. success

Para , 0011

S(0011)A(0,011)A(ε,ε)A(1,1)A(1,1)ε

Ahora, Boullier muestra en el documento vinculado anteriormente que existe un algoritmo de tiempo polinómico de programación dinámica para RCG, que responde a su pregunta si la gramática anterior es correcta. La idea es que, aunque presenté las instancias de las variables , , etc. como cadenas, realmente son intervalos dentro de la cadena de entrada, que se pueden tabular correctamente.XY

Sylvain
fuente
¿Hay alguna derivación que lleve S (0011) a ? (Debería haber uno.)ϵ
Radu GRIGore
No lo creo.
Serge Gaspers
Además, A (10,011010) -> A (0,101) A (0,0) -> , pero creo que 10011010 no es un cuadrado. ϵ
Radu GRIGore
Gracias por las devoluciones; He cambiado un poco la gramática e incluso tengo una pequeña intuición de que podría funcionar.
Sylvain
3
De nada. Aquí hay más, para la gramática actualizada :) A (00,000110) -> A (0,011) A (0,0) -> , pero 00000110 no es un cuadrado. Además, parece que no hay derivación para 100110101010, que es un cuadrado. ϵ
Radu GRIGore
1

Actualización: Como Tsuyoshi Ito señala en los comentarios, este algoritmo tiene un tiempo de ejecución exponencial.

Publicación original:

Así es como programaría esto en el mundo real.

Se nos da una cadena S = (S [1], ..., S [n]). Para cada prefijo S_r = (S [1], ..., S [r]), hay un conjunto {(T_i, U_i)} de pares de cadenas, de modo que S_r es una combinación de (T_i, U_i), y T_i es un prefijo de U_i (es decir, U_i 'comienza con' T_i). S_r en sí es un cuadrado si y solo si este conjunto contiene un par (T_i, U_i) con T_i = U_i.

Ahora, no necesitamos generar todos estos pares; solo necesitamos generar el sufijo V_i de cada cadena U_i obtenida eliminando su copia de T_i. Esto eliminará un número (posiblemente exponencial) de duplicados irrelevantes. Ahora S_r es un cuadrado si y solo si este conjunto de sufijos contiene la cadena vacía. Entonces el algoritmo se convierte en:

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.

Por ejemplo, si S es 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}

Podemos descartar todos los sufijos que tengan más de la mitad del largo de la cadena de entrada, por lo que esto se simplifica a:

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}

He programado esto en C ++, y funciona en todos los ejemplos dados aquí. Puedo publicar el código, si alguien está interesado. La pregunta es: ¿puede el tamaño de SuffixSet crecer más rápido que polinomialmente?

TonyK
fuente
3
También probé esto, pero los experimentos muestran que el tamaño de SuffixSet parece crecer exponencialmente en n si la cadena original es (AB) ^ n.
Tsuyoshi Ito
1

EDITAR: Esta es una respuesta incorrecta.


Sylvain sugirió un RCG que desafortunadamente no era apropiado para estos "cuadrados aleatorios". Sin embargo, creo que hay uno (EDITAR: ¡no un RCG, vea los comentarios de Kurt a continuación!) , Que se ve de la siguiente manera:

S(Y)A(ϵ,Y)(1)A(X,ZY)A(XZ,Y)(2)A(aX,aY)A(X,Y) for every aΣ(3)A(ϵ,ϵ)ϵ(4)

Explicación: recordar que tenemos para que coincida con los símbolos que pueden aparecer en cualquier parte de la cadena, pero una vez que hemos emparejado y'sólo podemos igualar y si implica ( que significa precedencia lineal). La idea es que separemos la cadena para comparar los prefijos de las mitades. Si los comienzos de dos subcadenas coinciden, podemos reducir el problema a las cadenas restantes . Si no, podemos transferir parte del lado derecho al lado izquierdoaabbabab(1,2)(3)(2)y ver si hay una coincidencia en una posición posterior. ¡Lo importante es que esto solo se permite en una dirección!

Aquí hay una derivación para (un contraejemplo al RCG de Sylvain):100110101010

S(100110101010)A(ϵ,100110101010)(1)A(1001,10101010)(2)A(01,101010)(3)A(011,01010)(2)A(1,010)(3)A(10,10)(2)A(ϵ,ϵ)(3)ϵ(4)

No he elaborado una prueba formal de que esta gramática capte exactamente los "cuadrados aleatorios", pero no debería ser demasiado difícil. Sylvain ya mencionó que el problema de decisión para los RCG es polinomial.

DaniCL
fuente
No veo cómo podría implementarse esto en tiempo polinómico: si comienza desde 000102030, puede alcanzar para x igual a cualquiera de las siguientes cadenas 123, 01230, 01203, 0012030, 01023, 0010230, 0010203, 000102030. (Sí, miré el documento vinculado por Sylvain, pero me parece todo francés.)2 3A(x,ϵ)23
Radu GRIGore
55
@DaniCL, Pensándolo bien ... ¿Los parámetros en el RHS de las reglas de producción deben ser rangos contiguos de la entrada? No vi que se establezca explícitamente en la definición en el artículo de Boullier, pero parece ser cómo se está utilizando. En el análisis del tiempo de ejecución del algoritmo de análisis, dice que el número de argumentos posibles para las cláusulas es O (n ^ 2h) donde h es la aridad máxima de las cláusulas yn es la longitud de entrada. En su gramática, XZ en general no será contiguo en la entrada original.
Kurt
3
@ Kurt, creo que encontraste la falla. En otro artículo ("Números chinos, MIX, codificación y gramáticas de concatenación de rango"), Boullier declara explícitamente: "Por supuesto, solo los rangos consecutivos pueden concatenarse en nuevos rangos. En cualquier PRCG, terminales, variables y argumentos en una cláusula son se supone que está vinculado a rangos por un mecanismo de sustitución ". Esto probablemente significa que mi gramática no es un RCG válido, que la duda de Radu era razonable y que este enfoque tampoco funciona.
DaniCL
2
@Kurt está en lo correcto. Sin la restricción de contigüidad, estoy bastante seguro de que puedo crear un conjunto de reglas de producción que reconocen el lenguaje NP-complete UNARY 3PARTITION. Cualquier conjunto de enteros no negativos se puede codificar en unario mediante una cadena en el idioma (1 * 0) ^ *. UNARY 3PARTITION es el conjunto de todas esas cadenas cuyo conjunto codificado puede dividirse en subconjuntos de 3 elementos, todos con la misma suma. (Ver en.wikipedia.org/wiki/3-partition_problem .)
Jeffε
1
Gramática para la PARTICIÓN UNARIA 3: S (X0Y0Z) -> A (e, X0, Y0, Z); A (W, 1X, Y, Z), A (W, X, 1Y, Z), A (W, X, Y, 1Z) -> A (W1, X, Y, Z); A (W, 0X, 0Y, 0Z) -> B (W, XYZ); B (W, e) -> e; B (W, X0Y0Z) -> C (W, W, X0, Y0, Z); C (W, 1V, 1X, Y, Z), C (W, 1V, X, 1Y, Z), C (W, 1V, X, Y, 1Z) -> C (W, V, X, Y, Z); C (W, e, X, Y, Z) -> B (W, XYZ)
Radu GRIGore