Algorithme efficace pour l'existence d'une permutation avec séquence de différences?

Cette question est motivée par ce post, pouvez-vous identifier la somme de deux permutations en temps polynomial? et mon intérêt pour les propriétés de calcul des permutations.

Une séquence de différences d'une permutation π de nombres 1 , 2 , … n + 1 est formée en trouvant la différence entre tous les deux nombres adjacents dans la permutation π . En d'autres termes, a i = | π ( i + 1 ) - π ( i ) | pour 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$

Par exemple, la séquence est la séquence de différences de permutation 2 3 4 1 . Alors que les séquences 2 , 2 , 3 et 3 , 1 , 2 ne sont pas la séquence des différences d'une permutation des nombres 1 , 2 , 3 , 4 .$1, 1, 3$$2 3 4 1$$2, 2, 3$$3, 1, 2$$1, 2, 3, 4$

Existe-t-il un algorithme efficace pour déterminer si une séquence donnée est la séquence des différences pour une permutation ou est-elle NP-difficile?$\pi$

EDIT : Nous obtenons un problème de calcul équivalent si nous formulons le problème en utilisant des permutations circulaires.

EDIT2 : Cross publié sur MathOverflow, Quelle est la difficulté de reconstruire une permutation à partir de sa séquence de différences?

EDIT3 Attribué la prime au croquis de preuve et j'accepterais la réponse après avoir obtenu la preuve formelle complète.

EDIT 4 : La belle preuve de complétude de Marzio a été publiée dans l'Electronic Journal of Combinatorics .$NP$

Voici une esquisse d'une réduction possible pour prouver qu'elle est dure NP:

$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)

Les trous doivent être remplis dans le reste de la permutation.

3) en utilisant un 1SEQ assez grand, suivi d'un 1SEQ avec quelques trous, suivi d'un autre 1SEQ grand, vous pouvez construire une ligne forcée ;

4) en rassemblant de nombreuses lignes forcées, vous pouvez créer un graphique de grille de permutation dans lequel les nœuds correspondent aux nombres manquants dans la permutation forcée sous-jacente.

Par exemple, la séquence 1111111112111111111112111111111 force le graphique de grille de permutation 5x7 suivant:

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) vous pouvez remplir tous les trous (c'est-à-dire terminer la permutation) si et seulement si le graphique de grille d'origine a un cycle hamiltonien

EDIT: 27 juillet 2013

J'ai essayé de prouver formellement l'intégralité du problème NP: j'ai introduit un nouveau problème (problème Crazy Frog ) qui est NPC. Le problème de la reconstruction par permutation à partir des différences est équivalent au «problème 1-D Crazy Frog sans cellules bloquées» (qui est également NPC).

Pour les détails de la réduction, voir ma question / réponse sur la théorie "Deux variantes de chemin hamiltonien" ou téléchargez un brouillon de la preuve "Quand une grenouille rencontre une permutation" :)) (Je vérifie / complète toujours)