What is the complexity class of arranging $1,\ldots, n$ so that all neighbors sum to a perfect square? I recently saw a problem from Numberphile here, where the goal is to arrange the numbers $1,\ldots,n$ so that the sum of adjacent numbers is a perfect square. This question from Mathematics Stack Exchange has a good analysis of the generalization of the problem for arbitrary powers, but I have been unable to find an analysis of the complexity class of the decision version of the problem. It is $NP$ since you can check if an arrangement satisfies the square sum condition efficiently, but I have been unable to come up with a better algorithm than creating the associated graph and solving the Hamiltonian path problem. 

So my question is if this problem is $NP$-complete or if there is a polynomial time algorithm that can decide if $1,\ldots,n$ can be arranged to satisfy the square-sum condition.

Arranging the integers means to find a permutation $a_1, \ldots, a_n$ of $1,\ldots, n$ with the property that for all $1 &lt; i &lt; n$, $a_i + a_{i+1}$ and $a_i + a_{i-1}$ are perfect squares.
Whether this problem is in NP or not (or rather, in NP or not known to be in NP) depends on how you encode the input. If you encode the input in binary (or in decimal), then the input "$N$" has length $n = O(\log N)$, whereas the obvious witness has length $\Theta(N\log N)$, which is exponential in $n$ (of course, there could be a more compact witness), giving a complexity upper bound of only NEXP. In contrast, if you encode the input in unary (that is, as $1^N$, i.e., $N$ times the symbol $1$), then the input length is $N$ as well, and so the witness has polynomial length, putting the problem in NP.

Even if you use the second encoding, it seems unlikely that the problem is NP-complete. Most NP-complete problems involve a lot of data, and even the few problems which have a constant number of integers as input have more than one integer as input. Of course, formally, speaking, you can think of the input to any problem as a single integer. But semantically, there is a big difference.

What is the complexity of the problem, then? If there is a nice characterization of the values of $N$ for which such an arrangement exists, then it is likely that implementing the characterization would put the problem in P (even using binary encoding). As an extreme example, if such an arrangement exists for all large enough $N$, or doesn't exist for all large enough $N$, then the problem can be solved in linear time. If there is no simple characterization, then the problem might indeed be difficult, but probably not NP-complete or NEXP-complete.