What is the complexity class of arranging $1,\ldots, n$ so that all neighbors sum to a perfect square?

Question

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 < i < n$, $a_i + a_{i+1}$ and $a_i + a_{i-1}$ are perfect squares.

Answer 1

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.

Answer 2

The following algorithm might solve the problem in constant time:

There is a solution iff n = 15, 16, 17, 23 or n >= 25. 

(You asked for a yes/no answer only, not for an actual solution). I most definitely can't prove that this algorithm is correct. It might be unprovable for all I know. I doubt that it is incorrect (for n = 50, there are thousands of solutions starting with the smallest possible numbers 1, 3 and 6)

PS The lexicographically first solution for n = 60 is:

1 3 6 10 15 21 4 5 11 14 50 31 18 7 2 34 30 19 45 36 13 51 49 32 17 47 53 28 8 56 25 39 42 58 23 41 59 22 27 54 46 35 29 20 44 37 12 52 48 33 16 9 55 26 38 43 57 24 40 60

Answer 3

I doubt that it's NP-complete.

As this comment on the question you linked points out, heuristically it's very likely that such an arrangement exists if $n$ is sufficiently large. In particular, we can build a graph on $n$ vertices, with an edge between two vertices if they sum to a perfect square. The graph has $\Theta(n^{1.5})$ edges. If we model this as a random graph, then it is overwhelmingly likely to have a Hamiltonian path. In particular, a result by Posa shows that if there are $\Omega(n \log n)$ edges, then the probability that there exists a Hamiltonian graph is $1-o(1)$ as $n \to \infty$. Subsequent results (e.g., Angluin and Valiant) show that the probability is in fact $1-O(n^{-c})$ for all $c>0$. This means that if the random graph is a good model for the structure of this graph, then once $n$ gets large enough, there almost surely exists such an arrangement.

In particular, this suggests that there is probably some number $n_0$ such that there is a valid arrangement for all $n \ge n_0$. This means there are only finitely many $n$ where no such arrangement exists. So, this immediately suggests a straightforward algorithm: it has hard-coded the list of all $n$ where such an arrangement does not exist. While finding the algorithm might be non-trivial, the algorithm does exist. Such an algorithm would run in $O(1)$ time.

So, the random graph model suggests that the problem can probably be solved by an $O(1)$-time algorithm. This makes it unlikely that the problem is NP-complete.

Disclaimer: None of this is a proof. The random graph model is a heuristic. The heuristic could fail if there is something that causes the structure of the graph to deviate significantly from that of a random graph. Personally, I don't really expect that to happen, but I don't have a proof that it doesn't happen.