[xulyrnew] Large optimization puzzle

Create an interesting but very difficult puzzle, allowing computer scientists to solve it over a very long time, perhaps centuries.  An optimization problem allows a solution to be improved over time, which seems nicer than having it remain unsolved until it is solved then forgotten.

For example, a very high dimensional Rubik's cube (twisty puzzle), scrambled using a specified determinstic pseudorandom number generator.  The goal is to find the shortest solving sequence.  This puzzle has the feature that some solution is known from the start: just reverse the initial scramble.  The high dimensional puzzle is interesting because of group theory, perhaps more interesting than just a very high-order 3-dimensional cube.  Can we design a harder puzzle based on other finite simple groups?

On the other hand, the Cunningham project already exists, and number theory is very interesting.

A cryptographic puzzle seems aesthetically not very interesting if based on symmetric cryptography primitives, e.g., AES, because symmetric cryptographic primitives are ugly compared to other elegant problems out there.

Inspired by, the traveling salesman problems for very large numbers of cities on Earth have been effectively solved.  We need something harder.