Algoritmo eficiente para la existencia de permutación con secuencia de diferencias?

Esta pregunta está motivada por esta publicación, ¿Puedes identificar la suma de dos permutaciones en el tiempo polinómico? , y mi interés en las propiedades computacionales de las permutaciones.

Una secuencia de diferencias de una permutación de los números se forma al encontrar la diferencia entre cada dos números adyacentes en la permutación . En otras palabras, para $a_1, a_2, \ldots a_n$ $\pi$ $1, 2, \ldots n+1$ $\pi$ $a_i= |\pi(i+1)-\pi(i)|$ $1 \le i \le n$

Por ejemplo, la secuencia es la secuencia de diferencias de permutación . Mientras que las secuencias y no son la secuencia de diferencias de cualquier permutación de los números . $1, 1, 3$ $2 3 4 1$ $2, 2, 3$ $3, 1, 2$ $1, 2, 3, 4$

¿Existe un algoritmo eficiente para determinar si una secuencia dada es la secuencia de diferencias para alguna permutación , o es NP-hard? $\pi$

EDITAR : Obtenemos un problema computacionalmente equivalente si formulamos el problema usando permutaciones circulares.

EDIT2 : Cross publicado en MathOverflow, ¿Qué tan difícil es reconstruir una permutación a partir de su secuencia de diferencias?

EDIT3 Otorgó la recompensa al boceto de prueba y aceptaría la respuesta después de obtener la prueba formal completa.

EDIT 4 : La agradable prueba de integridad Marzio se ha publicado en el Electronic Journal of Combinatorics . $NP$

cc.complexity-theory co.combinatorics np-hardness permutations Mohammad Al-Turkistany
fuente

Quizás otro comentario trivial (¿pero más sólido?) Es que si

es una permutación de

(todos los valores son distintos), entonces el problema es verificar que la secuencia sea un etiquetado elegante de la línea de

nodos que se pueden resolver en tiempo polinómico.

a_{i}

$a_i$

[1.. n]

$[1..n]$

n + 1

$n+1$

Marzio De Biasi

@MarzioDeBiasi Creo que compartes mi pasión por los problemas de permutación. Espero haber encontrado el problema de permutación más simple computacionalmente interesante :)

Mohammad Al-Turkistany

:-) ... Prefiero decir que mi comentario proviene directamente de las horas que pasé en vano sobre el problema del etiquetado de árboles agraciados ... sin embargo, tengo una idea difusa de una posible reducción de NP-completo para su problema; si logro formalizarlo, publicaré una respuesta.

Marzio De Biasi

@MarzioDeBiasi Encontré este interesante comentario de Shor afirmando que su problema, la programación de trabajos con un problema de cuello de botella , es equivalente a un caso especial de mi problema. Aquí está el comentario de Shor: si

, el problema es equivalente a encontrar una permutación de

para que

K = 2 N

$K=2N$

1...2 N

$1...2N$

i_{2 a - 1} - i_{2 a} = A_{i}

$i_{2a−1}−i_{2a}=A_i$ . Esto proporciona otra prueba de la completitud

de mi problema.

N P

$NP$

Mohammad Al-Turkistany

Respuestas:

Este es un boceto de una posible reducción para demostrar que es NP-hard:

$a_i$ $...11111...$

$2$ $1112112111$

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)

Los agujeros deben rellenarse en el resto de la permutación.

3) usando un 1SEQ lo suficientemente grande, seguido de un 1SEQ con algunos agujeros, seguido de otro 1SEQ grande, puede construir una línea forzada ;

4) juntando muchas líneas forzadas, puede construir un gráfico de cuadrícula de permutación en el que los nodos corresponden a los números que faltan en la permutación forzada subyacente.

Por ejemplo, la secuencia 1111111112111111111112111111111, fuerza el siguiente gráfico de cuadrícula de permutación 5x7:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14   
 1  2  3  4  5  6  7

$w \times w$ $a,b$ $|a-b|=kw$

$G$

$G$ $G$

7) puede llenar todos los agujeros (es decir, completar la permutación) si y solo si el gráfico de cuadrícula original tiene un ciclo hamiltoniano

EDITAR: 27 de julio de 2013

Traté de demostrar formalmente la completitud NP del problema: introduje un nuevo problema (problema de Crazy Frog ) que es NPC. El problema de Reconstrucción de permutación a partir de diferencias es equivalente al "problema de la rana loca 1-D sin celdas bloqueadas" (que también es NPC).

Para los detalles de la reducción, vea mi pregunta / respuesta en la teoría "Dos variantes del camino hamiltoniano" o descargue un borrador de la prueba "Cuando una rana se encuentra con una permutación" :)) (Todavía lo estoy revisando / completando)

Marzio De Biasi
fuente

Bien, estoy seguro de que esto conducirá a una solución, el gadget de selección es definitivamente realizable.

domotorp

@domotorp: lo publiqué (publicaré los detalles de selección / sincronización de la pieza en los próximos días); quizás contiene un error que no veo, sin embargo, apuesto $ 1 a que toda la reducción se puede simplificar enormemente :-)

Marzio De Biasi

@MarzioDeBiasi Buena visualización. Parece que estás en el camino correcto. ¿Podría publicar su respuesta en MathOverflow ya que hay un interés considerable en el problema?

Mohammad Al-Turkistany

@MarzioDeBiasi ¿Podría publicar su respuesta final (formal) antes de que expire la recompensa?

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Acabo de regresar de un viaje, intentaré formalizar (y consultar con un CSP) los dispositivos en los próximos días.

Marzio De Biasi