-1

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?

Janoma
  • 1,406
  • 11
  • 27
bitmask
  • 361
  • 2
  • 11
  • 10
    $2^{n \log n}$ would put it in EXP. – Suresh Venkat Sep 16 '11 at 15:38
  • well you know that n^n > n! for all n>=2... – ratchet freak Sep 16 '11 at 16:07
  • 6
    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
  • @Chao Xu: That certainly has that complexity, but I was more interested in problems that have actual applications. – bitmask Sep 16 '11 at 18:45
  • 20
    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
  • how is this not off topic? – Sasho Nikolov Sep 20 '11 at 02:15
  • @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. – Kaveh Sep 21 '11 at 19:25
  • 2
    @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
  • @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 Sep 23 '11 at 00:47
  • 2
    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 02:22
  • @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 Sep 23 '11 at 13:21

3 Answers3

6

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.

Community
  • 1
Janoma
  • 1,406
  • 11
  • 27
-2

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

Chad Brewbaker
  • 2,359
  • 15
  • 18
-14

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

Parag
  • 101