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$ – Suresh Venkat Sep 16 '11 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 '11 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$ – Tsuyoshi Ito Sep 16 '11 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$ – Sasho Nikolov Sep 21 '11 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$ – 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.

| cite | improve this answer | |

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

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ I think that an answer like this is better suited as a comment. $\endgroup$ – Timothy Sun Sep 19 '11 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$ – Aaron Sterling Sep 19 '11 at 19:16
  • $\begingroup$ Oh, I completely forgot about that. $\endgroup$ – Timothy Sun Sep 19 '11 at 19:23
  • 12
    $\begingroup$ -1, this is not correct. $\endgroup$ – Kaveh Sep 19 '11 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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