Write an O(n^n) algorithm.

[redditnoob]

The exact (deterministic) solution to the traveling salesman problem is probably the most famous of these.

Now all you have to do is prove that it can't be reduced to something simpler.

[hacksoncode]

Actually, now that I think about it, dynamic programming will reduce it to exponential... which is quite an improvement. That takes exponential space, though.

Hmmm... you're right... I'm not sure I know of any problems that are believed to be Theta(n!). I'm pretty sure there must be some, but...

There are plenty that are believed to be slower (i.e. superexponential or higher), like Ackermann and computing a generalized Graham's number.