I was just wondering if there is a problem whose best solution (under common assumptions) has time complexity $\Theta(n^n)$. And what complexity class would that belong to?

  • 10
    $\begingroup$ $2^{n \log n}$ would put it in EXP. $\endgroup$ Sep 16, 2011 at 15:38
  • 6
    $\begingroup$ Trivial one: List all strings with length equal to the alphabet size. Here $n$ is the size of the alphabet. $\endgroup$
    – Chao Xu
    Sep 16, 2011 at 16:58
  • 20
    $\begingroup$ Some motivation to your question would be nice. Without motivation, this question is only as interesting as similar (hypothetical) questions such as “What are examples of Θ(3^n)-time problems?” “What are examples of Θ(n^(n/2))-time problems?” “What are examples of Θ(n log log n)-time problems?” and so on; in short, it is not interesting. $\endgroup$ Sep 16, 2011 at 19:00
  • 2
    $\begingroup$ @Kaveh: I don't see two professors, asking each other "hey, do you think any problems have complexity $\Theta(n^n)$" :) even if one of them is not a theorist, I still don't see this happening. So by that criterium, this is not research-level. The subquestion about what complexity class this belongs to is easily answered by wikipedia (which is maybe what you meant with the link?) $\endgroup$ Sep 21, 2011 at 20:24
  • 2
    $\begingroup$ People who want to close it should vote accordingly. I'm a little on the fence on this one. $\endgroup$ Sep 23, 2011 at 2:22

3 Answers 3


Following a question I asked recently, I think the following problem is $\Theta(n^n)$:

Given a DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ with $n$ states, compute the syntactic monoid of $L=L(\mathcal{A})$.

Or, if you prefer a decision problem:

Given a DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ with $n$ states and a finite monoid $M$, is $M$ isomorphic to the syntactic monoid of $L(\mathcal{A})$?

Let's justify the bound. Assume $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ is minimal. The size of the syntactic monoid of $L$ is the index of the following equivalence relation:

$x\sim y$ iff for all $u,v\in\Sigma^*$, $uxv\in L$ if and only if $uyv\in L$.

The following is a characterization of this relation when $L$ is regular:

Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for $L$. Then $x\sim y$ if and only if for every $q\in Q$, $\hat\delta(q,x)=\hat\delta(q,y)$.

Now, assume $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ is fixed and consider the following notation: for $q\in Q$, $L_q$ is the language accepted by the automaton $(Q,\Sigma,\delta,q,F)$, that is, $\mathcal{A}$ with a (possibly) different initial state. In particular, $L=L_{q_0}$. Consider now the relation used for the Myhill-Nerode theorem (the one for the minimal DFA):

$x\equiv_Ly$ iff for all $z\in\Sigma^*$, $xz\in L$ if and only if $yz\in L$,

which is characterized with minimal automata:

Given a minimal DFA $\mathcal{A}$ for $L$, $x\equiv_Ly$ iff $\hat\delta(q_0,x)=\hat\delta(q_0,y)$

With this, we can rewrite the previous characterization as follows:

Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for $L$. Then $x\sim y$ if and only if for every $q\in Q$, $x\equiv_{L_q} y$.

Now, the index of $\equiv_{L_q}$ is equal to the size of the minimal DFA that accepts $L_q$, and this number is bounded by $n$. Thus, the index of $\sim$ is bounded by $n^n$.

This should give you a rough idea. I think the tightness of the bound is proved in this paper.


Any algorithm that iterates once over a set of size $n^n$; such as all length $n$ strings on a size $n$ alphabet.


I do not know the example but yes n^n will belong to class NP ...

  • $\begingroup$ I think that an answer like this is better suited as a comment. $\endgroup$ Sep 19, 2011 at 19:09
  • 2
    $\begingroup$ @TimothySun: Parag does not yet have the reputation points needed in order to leave comments. It is a StackExchange anti-spam device. $\endgroup$ Sep 19, 2011 at 19:16
  • $\begingroup$ Oh, I completely forgot about that. $\endgroup$ Sep 19, 2011 at 19:23
  • 12
    $\begingroup$ -1, this is not correct. $\endgroup$
    – Kaveh
    Sep 19, 2011 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.