Permutation Reconstruction from Differences
classification
💻 cs.CC
keywords
differencespermutationdotscprovepuzzlereconstructionabsolutebeen
pith:YIXFT3XD Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{YIXFT3XD}
Prints a linked pith:YIXFT3XD badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
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 NP-complete. As an intermediate step we first prove the 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.