Geodesic
Permutation reconstruction from differences
Marzio De Biasi1
1No affiliation
The electronic journal of combinatorics, Tome 21 (2014) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that the problem of reconstructing a permutation $\pi_1,\dotsc,\pi_n$ of the integers $[1\dotso n]$ given the absolute differences $|\pi_{i+1}-\pi_i|$, $i = 1,\dotsc,n-1$ is $\sf{NP}$-complete. As an intermediate step we first prove the $\sf{NP}$-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.An addendum was added to this paper on the 9th of December 2015.
DOI : 10.37236/4086
Classification : 68Q17, 05A05
Mots-clés : permutation reconstruction, NP-completeness

Marzio De Biasi  1

1 No affiliation 
@article{10_37236_4086,
     author = {Marzio De Biasi},
     title = {Permutation reconstruction from differences},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {4},
     doi = {10.37236/4086},
     zbl = {1298.68098},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4086/}
}
TY  - JOUR
AU  - Marzio De Biasi
TI  - Permutation reconstruction from differences
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4086/
DO  - 10.37236/4086
ID  - 10_37236_4086
ER  - 
%0 Journal Article
%A Marzio De Biasi
%T Permutation reconstruction from differences
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4086/
%R 10.37236/4086
%F 10_37236_4086
Marzio De Biasi. Permutation reconstruction from differences. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4086

Cité par Sources :