Permutation Reconstruction from Differences

[摘要] 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}$

[学科分类] 离散数学和组合数学

[关键词] permutation reconstruction;NP-completeness