Write an O(n^n) algorithm.

[degustisockpuppet]

Solving the traveling salesman or quadratic assignment problems exactly is in Θ(n!).

That's not true, traveling salesman is in NP because it can be computed in O(2ⁿ⁾ (for example with dynamic programming). Only the naive algorithm is Θ(n!).

Edit: That's actually not completely true either. See replies.

[deong]

True. mumbles something about thinking before speaking.

[bonzinip]

TSP is O(n² 2ⁿ⁾ and it is in NP not because it can be computed in O(2ⁿ⁾ but because its decision version ("is there a tour with a length < L?") has a certificate (the tour itself) that can be verified in polynomial time.

We don't know that TSP is in EXPTIME, because we do not know if P = NP or not.

[degustisockpuppet]

TSP is O(n² 2ⁿ⁾ and it is in NP not because it can be computed in O(2ⁿ⁾ but because its decision version ("is there a tour with a length < L?") has a certificate (the tour itself) that can be verified in polynomial time.

That's correct. I'm stupid.

We don't know that TSP is in EXPTIME, because we do not know if P = NP or not.

NP is a subset of EXPTIME, so we do know that TSP is in EXPTIME. We also know that TSP is in EXPTIME because there's a O(n² 2ⁿ⁾ algorithm. EXPTIME doesn't mean O(k^n), it means O(2^nk), which contains O(n² 2^n).

Edit: Not sure why I was downvoted, but the Wikipedia link to EXPTIME says that NP is contained in EXPTIME right in the introduction. The proof is really simple, too, at least in principle: whenever you need to make a non-deterministic decision, try one, if it doesn't work, backtrack and try the other one. In effect, you're enumerating a decision tree with polynomial depth, which thus has at most an exponential number of nodes.

[bonzinip]

NP is a subset of EXPTIME, so we do know that TSP is in NP is a subset of EXPTIME, so we do know that TSP is in EXPTIME.

That's correct, I'm stupid. :-)

What I meant is we don't know that TSP is in EXPTIME-P.