Is there a problem in Computer science that:
* Can't be solved in polynomial time
* Can be solved in faster than exponential time
By the way, one Galaxy feature request:
* Add a feature that checks whether it is possible for a game to be stuck in an infinite loop. This feature must work all the time, and it must not, itself, get stuck in an infinite loop.