<p>Quoting the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q" rel="noreferrer">complexity zoo</a>:</p>
<blockquote>
<p><strong>QP</strong>: Quasipolynomial-Time</p>
<p>Equals DTIME(2<sup>polylog(n)</sup>).</p>
<hr />
<p><strong>QPLIN</strong>: Linear Quasipolynomial-Time</p>
<p>Equals DTIME(n<sup>O(log n)</sup>).</p>
<p>Has the same relationship to <strong>QP</strong> that <strong>E</strong> does to <strong>EXP</strong>.</p>
</blockquote>
<p>Both these classes exist. I know that Quasipolynomial-time algorithms arise frequently in many areas. A google search will reveal several known quasipolynomial-time algorithms. Some of these may actually be QPLIN algorithms.</p>
<p>One of the advantages of QP over QPLIN is that it's more robust. For example, it is closed under composition, so if you have a quasipolynomial-time subroutine that takes an input of size <span class="math-container">$n$</span> to an input of size <span class="math-container">$n^{\log n}$</span> and now run a quasipolynomial-time algorithm on this new input, you will have an algorithm that runs in <span class="math-container">$O(n^{\textrm{polylog}(n)})$</span> time.</p>

CC BY-SA 3.0
2014-05-10T04:13:36.913Z
This earlier question and its answers are closely related: http://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n/21660#21660
Andras Farago
CC BY-SA 3.0
2014-05-09T17:52:45.047Z
2014-05-09T17:52:45.047Z
2020-06-17T09:38:08.363Z
Robin Kothari
<p>There are complexity classes like LOGNP or LOGSNP (see [2]) whose problems typically have this kind of running time, like restrictions of NP where only logarithmically many non-deterministic steps are allowed.</p>

<p>Take a look at the following papers (the first two are also available on citeseer, can be found via a search engine):</p>

<p>[1] Judy Goldsmith, Matthew A. Levy, Martin Mundhenk. Limited nondeterminism.
<a href="http://dl.acm.org/citation.cfm?doid=235767.235769" rel="nofollow">http://dl.acm.org/citation.cfm?doid=235767.235769</a></p>

<p>[2] Christos H. Papadimitriou, Mihalis Yannakakis. On Limited Nondeterminism and the Complexity of the V-C Dimension.
<a href="http://www.sciencedirect.com/science/article/pii/S0022000096900586" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0022000096900586</a></p>

<p>[3] Liming Cai, Jianer Chen. On the Amount of Nondeterminism and the Power of Verifying.
<a href="http://epubs.siam.org/doi/abs/10.1137/S0097539793258295" rel="nofollow">http://epubs.siam.org/doi/abs/10.1137/S0097539793258295</a></p>

CC BY-SA 3.0
2014-05-09T17:31:20.383Z
2014-05-09T17:31:20.383Z
Florent Foucaud
<p>Do languages decidable in deterministic $n^{O(\log n)}$ time form an interesting complexity class? If yes, is there a name for this class and are there some interesting properties about it that we know about? If not, why not (can we derive it properties easily from some other known complexity class)?</p>

<p>Thank you!</p>

CC BY-SA 3.0
2014-05-09T16:55:53.997Z
Complexity classes are usually not defined by running time functions. But e.g the running time you mentioned is a subset of $2^{n^{o(1)}}$, which are known as subexponential running time. Might you like to read about [ETH](http://en.wikipedia.org/wiki/Exponential_time_hypothesis).
Saeed
CC BY-SA 3.0
2014-05-09T17:18:22.323Z
"Complexity classes are usually not defined by running time functions": It depends what you mean by *usually*. With [Blum complexity measures](http://en.wikipedia.org/wiki/Blum_complexity_measure), complexity classes *are* defined by running time functions, and one can prove that $\mathsf P$ for instance can be defined by some running time function (which is, needless to say, not a polynomial function nor any *natural* function).
Bruno
CC BY-SA 3.0
2014-05-09T17:21:28.607Z
To be accurate, $n^{O(\log n)} = \mathrm e^{O(\log^2 n)}$ isn't a single function, but a family of functions. The class $\mathsf P$ similarly corresponds to problems solvable by deterministic computations in $n^{O(1)} = \mathrm e^{O(\log n)}$ time.
Niel de Beaudrap
CC BY-SA 3.0
2014-05-09T17:26:50.370Z
@Bruno, first of all I said running time function not an arbitrary function. Second I provide a much more better sample than your irrelivant example, so I think the meaning of usually is clear from the context. Note that whatever has complexity in its name doesn't mean is related to this question.
Saeed
CC BY-SA 3.0
2014-05-09T17:45:41.943Z
@Saeed: Of course, my comment was an aside (a comment in some sense...) and not an answer to the question. Yet, I still do not agree with the fact that "complexity classes are not defined by running time functions." It depends on the context, and on the complexity classes. And regarding the question, as Niel correctly says, $n^{O(\log n)}$ is not a function but a family of function so I do not see any problem considering the complexity class, say $\mathsf{QuasiP}$, defined by this expression.
Bruno
CC BY-SA 3.0
2014-05-09T19:13:14.190Z
@Bruno, somehow agreed, I already in my first comment said that it's a subset not a function (implicitly), but I also at that moment forgot about QusiP to mention it. But I think you are also agree that if we look at a good tcs conference just a few percentage of papers are using these sort of classifications.
Saeed
<complexity-classes>
Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class?
simpleton
# Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class?

(Asked by: username_0 on 2014-05-09)

Do languages decidable in deterministic $n^{O(\log n)}$ time form an interesting complexity class? If yes, is there a name for this class and are there some interesting properties about it that we know about? If not, why not (can we derive it properties easily from some other known complexity class)?

Thank you!

**Tags:** complexity-classes
> **Comments:**
> **username_1**: Complexity classes are usually not defined by running time functions. But e.g the running time you mentioned is a subset of $2^{n^{o(1)}}$, which are known as subexponential running time. Might you like to read about [ETH](http://en.wikipedia.org/wiki/Exponential_time_hypothesis).  
> **username_2**: "Complexity classes are usually not defined by running time functions": It depends what you mean by *usually*. With [Blum complexity measures](http://en.wikipedia.org/wiki/Blum_complexity_measure), complexity classes *are* defined by running time functions, and one can prove that $\mathsf P$ for instance can be defined by some running time function (which is, needless to say, not a polynomial function nor any *natural* function).  
> **username_3**: To be accurate, $n^{O(\log n)} = \mathrm e^{O(\log^2 n)}$ isn't a single function, but a family of functions. The class $\mathsf P$ similarly corresponds to problems solvable by deterministic computations in $n^{O(1)} = \mathrm e^{O(\log n)}$ time.  
> **username_1**: @Bruno, first of all I said running time function not an arbitrary function. Second I provide a much more better sample than your irrelivant example, so I think the meaning of usually is clear from the context. Note that whatever has complexity in its name doesn't mean is related to this question.  
> **username_2**: @Saeed: Of course, my comment was an aside (a comment in some sense...) and not an answer to the question. Yet, I still do not agree with the fact that "complexity classes are not defined by running time functions." It depends on the context, and on the complexity classes. And regarding the question, as Niel correctly says, $n^{O(\log n)}$ is not a function but a family of function so I do not see any problem considering the complexity class, say $\mathsf{QuasiP}$, defined by this expression.  
> **username_1**: @Bruno, somehow agreed, I already in my first comment said that it's a subset not a function (implicitly), but I also at that moment forgot about QusiP to mention it. But I think you are also agree that if we look at a good tcs conference just a few percentage of papers are using these sort of classifications.  

---

## 2 answers

### Answer by username_4 on 2014-05-09. Score: 11

Quoting the [complexity zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q):

> **QP**: Quasipolynomial-Time
>
> Equals DTIME(2polylog(n)).
>
> ---
>
> **QPLIN**: Linear Quasipolynomial-Time
>
> Equals DTIME(nO(log n)).
>
> Has the same relationship to **QP** that **E** does to **EXP**.

Both these classes exist. I know that Quasipolynomial-time algorithms arise frequently in many areas. A google search will reveal several known quasipolynomial-time algorithms. Some of these may actually be QPLIN algorithms.

One of the advantages of QP over QPLIN is that it's more robust. For example, it is closed under composition, so if you have a quasipolynomial-time subroutine that takes an input of size $n$ to an input of size $n^{\log n}$ and now run a quasipolynomial-time algorithm on this new input, you will have an algorithm that runs in $O(n^{\textrm{polylog}(n)})$ time.

> **Comments:**
> **username_5**: This earlier question and its answers are closely related: http://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n/21660#21660  

---

### Answer by username_6 on 2014-05-09. Score: 4

There are complexity classes like LOGNP or LOGSNP (see [2]) whose problems typically have this kind of running time, like restrictions of NP where only logarithmically many non-deterministic steps are allowed.

Take a look at the following papers (the first two are also available on citeseer, can be found via a search engine):

[1] Judy Goldsmith, Matthew A. Levy, Martin Mundhenk. Limited nondeterminism.
<http://dl.acm.org/citation.cfm?doid=235767.235769>

[2] Christos H. Papadimitriou, Mihalis Yannakakis. On Limited Nondeterminism and the Complexity of the V-C Dimension.
<http://www.sciencedirect.com/science/article/pii/S0022000096900586>

[3] Liming Cai, Jianer Chen. On the Amount of Nondeterminism and the Power of Verifying.
<http://epubs.siam.org/doi/abs/10.1137/S0097539793258295>


---

