Mi interés en la combinatoria motivado problemas de cálculo me llevó a la búsqueda de problemas simples que resultan ser computacionalmente difícil. En esta búsqueda, me encontré con un problema que espero es NP-completo. He buscado en la literatura, sin encontrar un equivalente o cerca de problema.
Motivado por este post, se Puede identificar la suma de dos permutaciones en el polinomio de tiempo? y mi interés en las propiedades de cálculo de las permutaciones.
Una de las diferencias de la secuencia de $a_1, a_2, \ldots a_n$ de una permutación $\pi$ de los números de $1, 2, \ldots n+1$ está formado por encontrar la diferencia entre cada dos números adyacentes en la permutación $\pi$. En otras palabras, $a_i= |\pi(i+1)-\pi(i)|$ para $1 \le i \le n$
Por ejemplo, secuencia $1, 1, 3$ es la diferencias de la secuencia de permutación $2 3 4 1$. Mientras, las secuencias de $2, 2, 3$ e $ 3, 1, 2$ no son las diferencias de la secuencia de cualquier permutación de los números de $1, 2, 3, 4$.
Existe un algoritmo eficiente para determinar si una determinada secuencia de las diferencias de la secuencia de algunos de permutación $\pi$, o es NP-duro?
Tenemos computacionalmente equivalentes problema si formulamos el problema utilizando permutaciones circulares.
Cruz publicado en TCS en SÍ, sin una respuesta. Algoritmo eficiente para la existencia de permutación con las diferencias de la secuencia?
EDITAR Marzio agradable NP-completitud de la prueba ha sido publicado en la Revista Electrónica de la Combinatoria.
