<p>Following a <a href="https://cstheory.stackexchange.com/questions/8285/on-the-relation-for-the-myhill-nerode-theorem-syntactic-monoid-of-a-language/8288">question I asked recently</a>, I think the following problem is $\Theta(n^n)$:</p>

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

<p>Or, if you prefer a decision problem:</p>

<blockquote>
  <p>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})$?</p>
</blockquote>

<p>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:</p>

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

<p>The following is a characterization of this relation when $L$ is regular:</p>

<blockquote>
  <p>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)$.</p>
</blockquote>

<p>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):</p>

<blockquote>
  <p>$x\equiv_Ly$ iff for all $z\in\Sigma^*$, $xz\in L$ if and only if $yz\in L$,</p>
</blockquote>

<p>which is characterized with minimal automata:</p>

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

<p>With this, we can rewrite the previous characterization as follows:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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$.</p>

<p>This should give you a rough idea. I think the tightness of the bound is proved in <a href="http://arxiv.org/abs/1010.3263" rel="nofollow noreferrer">this paper</a>.</p>

CC BY-SA 3.0
2011-09-22T22:08:38.070Z
2011-09-22T22:08:38.070Z
2017-04-13T12:32:28.117Z
Janoma
<p>Any algorithm that iterates once over a set of size $n^n$; such as all length $n$ strings on a size $n$ alphabet.</p>

CC BY-SA 3.0
2011-09-21T21:21:50.297Z
2011-09-21T21:21:50.297Z
Chad Brewbaker
<p>I do not know the example but yes n^n will belong to class NP ...</p>

CC BY-SA 3.0
2011-09-19T19:09:47.363Z
I think that an answer like this is better suited as a comment.
Timothy Sun
CC BY-SA 3.0
2011-09-19T19:16:37.080Z
@TimothySun: Parag does not yet have the reputation points needed in order to leave comments.  It is a StackExchange anti-spam device.
Aaron Sterling
CC BY-SA 3.0
2011-09-19T19:23:51.770Z
Oh, I completely forgot about that.
Timothy Sun
CC BY-SA 3.0
2011-09-19T20:07:32.683Z
-1, this is not correct.
Kaveh
CC BY-SA 3.0
2011-09-19T18:47:54.207Z
2011-09-19T18:47:54.207Z
Parag
<p>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?</p>

CC BY-SA 3.0
2011-09-16T15:38:23.900Z
$2^{n \log n}$ would put it in EXP.
Suresh Venkat
CC BY-SA 3.0
2011-09-16T16:07:06.100Z
well you know that `n^n > n!` for all n>=2...
ratchet freak
CC BY-SA 3.0
2011-09-16T16:58:26.150Z
Trivial one: List all strings with length equal to the alphabet size. Here $n$ is the size of the alphabet.
Chao Xu
CC BY-SA 3.0
2011-09-16T18:45:20.760Z
@Chao Xu: That certainly has that complexity, but I was more interested in problems that have actual applications.
bitmask
CC BY-SA 3.0
2011-09-16T19:00:16.480Z
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
CC BY-SA 3.0
2011-09-20T02:15:42.580Z
how is this not off topic?
Sasho Nikolov
CC BY-SA 3.0
2011-09-21T19:25:00.647Z
@Sasho, so far no one has said that the question is off-topic. (But IMHO the question doesn't seem to be a research-level question and therefore is probably off-topic and more suitable for Math.SE). The problem given by Chao is a real world problem. Also check [this](http://cstheory.stackexchange.com/faq#questions-should-be-based-on-knowledge-sharing-not-on-shirking).
Kaveh
CC BY-SA 3.0
2011-09-21T20:24:53.420Z
@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
CC BY-SA 3.0
2011-09-23T00:47:46.510Z
@Kaveh I agree with you and Sasho, this question is not research level and should be migrated to math.SE. I do not have the rep to cast close votes, but this is my virtual close-vote.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-23T02:22:44.970Z
People who want to close it should vote accordingly. I'm a little on the fence on this one.
Suresh Venkat
CC BY-SA 3.0
2011-09-23T13:21:51.737Z
@Artem, right now the question doesn't have any close votes, so I don't think it is as clear cut as you say. In addition, migrating questions has been controversial, there is no should for migration, if the OP wants he/she can repost it on Math.SE without migration. (I don't migrate questions unless I am casting the last close vote and it is clear that the question is very unlikely to be reopened here).
Kaveh
<cc.complexity-theory><time-complexity>
Examples for $\Theta(n^n)$ problems
bitmask
# Examples for $\Theta(n^n)$ problems

(Asked by: username_0 on 2011-09-16)

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?

**Tags:** cc.complexity-theory, time-complexity

> **Comments:**
> **username_1**: $2^{n \log n}$ would put it in EXP.  
> **username_2**: well you know that `n^n > n!` for all n>=2...  
> **username_3**: Trivial one: List all strings with length equal to the alphabet size. Here $n$ is the size of the alphabet.  
> **username_0**: @username_3: That certainly has that complexity, but I was more interested in problems that have actual applications.  
> **username_4**: 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.  
> **username_5**: how is this not off topic?  
> **username_6**: @Sasho, so far no one has said that the question is off-topic. (But IMHO the question doesn't seem to be a research-level question and therefore is probably off-topic and more suitable for Math.SE). The problem given by Chao is a real world problem. Also check [this](http://cstheory.stackexchange.com/faq#questions-should-be-based-on-knowledge-sharing-not-on-shirking).  
> **username_5**: @username_6: 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?)  
> **username_7**: @username_6 I agree with you and Sasho, this question is not research level and should be migrated to math.SE. I do not have the rep to cast close votes, but this is my virtual close-vote.  
> **username_1**: People who want to close it should vote accordingly. I'm a little on the fence on this one.  
> **username_6**: @Artem, right now the question doesn't have any close votes, so I don't think it is as clear cut as you say. In addition, migrating questions has been controversial, there is no should for migration, if the OP wants he/she can repost it on Math.SE without migration. (I don't migrate questions unless I am casting the last close vote and it is clear that the question is very unlikely to be reopened here).  

---

## 3 answers

### Answer by username_8 on 2011-09-22. Score: 6 | Accepted answer

Following a [question I asked recently](https://cstheory.stackexchange.com/questions/8285/on-the-relation-for-the-myhill-nerode-theorem-syntactic-monoid-of-a-language/8288), 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](http://arxiv.org/abs/1010.3263).


---

### Answer by username_9 on 2011-09-21. Score: -2

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


---

### Answer by username_10 on 2011-09-19. Score: -14

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

> **Comments:**
> **username_11**: I think that an answer like this is better suited as a comment.  
> **username_12**: @TimothySun: username_10 does not yet have the reputation points needed in order to leave comments.  It is a StackExchange anti-spam device.  
> **username_11**: Oh, I completely forgot about that.  
> **username_6**: -1, this is not correct.  

---

