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?
$\begingroup$
$\endgroup$
11
-
10$\begingroup$ $2^{n \log n}$ would put it in EXP. $\endgroup$– Suresh VenkatSep 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 XuSep 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$– Tsuyoshi ItoSep 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$– Sasho NikolovSep 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$– Suresh VenkatSep 23, 2011 at 2:22
|
Show 6 more comments
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Any algorithm that iterates once over a set of size $n^n$; such as all length $n$ strings on a size $n$ alphabet.
$\begingroup$
$\endgroup$
4
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
-
-
12