# Examples for $\Theta(n^n)$ problems

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?

• $2^{n \log n}$ would put it in EXP. – Suresh Venkat Sep 16 '11 at 15:38
• Trivial one: List all strings with length equal to the alphabet size. Here $n$ is the size of the alphabet. – Chao Xu Sep 16 '11 at 16:58
• 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. – Tsuyoshi Ito Sep 16 '11 at 19:00
• @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?) – Sasho Nikolov Sep 21 '11 at 20:24
• People who want to close it should vote accordingly. I'm a little on the fence on this one. – Suresh Venkat Sep 23 '11 at 2:22

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

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