Algoritmo eficiente para existência de permutação com sequência de diferenças?

Esta questão é motivada por este post. Você consegue identificar a soma de duas permutações no tempo polinomial? , e meu interesse em propriedades computacionais de permutações.

Uma sequência de diferenças de uma permutação dos números é formada pela descoberta da diferença entre cada dois números adjacentes na permutação . Em outras palavras,para π 1 , 2 , … n + 1 π a i = | π ( i + 1 ) - π ( i ) | 1 ≤ i ≤ $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 exemplo, a sequência é a sequência de diferenças da permutação . Embora as sequências e não sejam a sequência de diferenças de qualquer permutação dos números .2 3 4 1 2 , 2 , 3 3 , 1 , 2 1 , 2 , 3 , $1, 1, 3$$2 3 4 1$$2, 2, 3$$3, 1, 2$$1, 2, 3, 4$

Existe um algoritmo eficiente para determinar se uma determinada sequência é a sequência de diferenças para alguma permutação ou é NP-difícil?$\pi$

EDIT : Obteremos problema computacionalmente equivalente se formularmos o problema usando permutações circulares.

EDIT2 : Cross postado no MathOverflow, Quão difícil é reconstruir uma permutação a partir de sua sequência de diferenças?

EDIT3 Concedeu a recompensa ao esboço da prova e eu aceitaria a resposta depois de obter a prova formal completa.

EDIT 4 : A boa prova de completude de Marzio foi publicada no Electronic Journal of Combinatorics .$NP$

Este é um esboço de uma possível redução para provar que é NP-difícil:

1) subsequências feitas de 1s (por exemplo ) (eu as chamo de 1SEQ) forçam uma subsequência de números crescentes ou decrescentes na permutação; . . .11111 . . $a_i$$...11111...$

2) se um valor for colocado em um 1SEQ longo, ele força um furo (um número ausente) e não altera a direção do 1SEQ. Por exemplo: força dois furos:$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)

Os furos devem ser preenchidos no restante da permutação.

3) usando um 1SEQ grande o suficiente, seguido por um 1SEQ com alguns orifícios, seguido por outro 1SEQ grande, você pode construir uma linha forçada ;

4) reunindo muitas linhas forçadas, é possível criar um gráfico de grade de permutação no qual os nós correspondam aos números ausentes na permutação forçada subjacente.

Por exemplo, a sequência 1111111112111111111112111111111, força o seguinte gráfico de grade de permutação 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

(ou sua versão simétrica). Observe que se a grade tiver tamanho e houver dois números ausentes na mesma coluna vertical, .a , b | a - b | = k $w \times w$$a,b$$|a-b|=kw$

5) o problema do ciclo hamiltoniano em gráficos de grade é NP-completo; então, dado um gráfico de grade (com furos), você pode criar o gráfico de grade de permutação equivalente;$G$

6) do último número da permutação, você pode "pular" para um número correspondente a um buraco (um nó em ) e, com uma sequência fixa de movimentos, você pode simular a travessia de ; isso requer um gadget bastante complexo - o "gadget de seleção" - que deve ser criado em outra parte do gráfico da grade de permutação;$G$$G$

7) você pode preencher todos os furos (isto é, completar a permutação) se e somente se o gráfico original tiver um ciclo hamiltoniano

EDIT: 27 de julho de 2013

Tentei provar formalmente a integridade do problema em NP: introduzi um novo problema (problema do Crazy Frog ), que é o NPC. O problema de reconstrução da permutação a partir das diferenças é equivalente ao "problema 1-D Crazy Frog sem células bloqueadas" (que também é NPC).

Para obter detalhes da redução, consulte minha pergunta / resposta na história "Duas variantes de caminho hamiltoniano" ou faça o download do rascunho da prova "Quando um sapo encontra uma permutação" :)) (ainda estou verificando / completando)