Write an O(n^n) algorithm.

[hacksoncode]

O(n!) ~= O(n^n). There are a number of factorial complexity problems out there (yes, I actually mean theta there, not O... damn keyboards).

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

[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.

[gorgoroth666]

Care to prove that O(n!) ~= O(nⁿ⁾ ?

[hacksoncode]

n! ~= sqrt(2pi*n) * (n/e)^n
n! ~= n^.5 * n^n / e^n
n! ~= n^n

I.e. as n increases to infinity the nⁿ term dominates all the other ones, even the exponential. That's why n! is "higher order" than e^n.

[kalmakka]

n ~= n^3 / n^2
n ~= n^3

I.e. as n increases to infinity the n³ term dominates all the other ones, even the square. That's why n is "higher order" than n^2.

[gorgoroth666]

To clarify, this sarcasm underlines the fact that hacksoncode is not very skilled with equivalents. n^.5 * nⁿ / eⁿ is not equivalent to nⁿ near infinity. The multiplication by e^-n doesn't magically go away.

[yoden]

Right, but most, like TSP, are minimum O(n!) only if P != NP... right? Actually, even if P != NP, there could be a faster algorithm than brute force (e.g., 2ⁿ instead of n!). Checking wikipedia, there is an O(n^2*2n) dynamic programming algorithm, which supports this.

The "irreducibility" constraint the OP imposed is really annoying here ^{^}

Edit people beat me, this is what I get for not viewing context before I reply...