5

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!

Sylvain
  • 3,374
  • 26
  • 22
simpleton
  • 75
  • 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. – Saeed May 09 '14 at 16:55
  • "Complexity classes are usually not defined by running time functions": It depends what you mean by usually. With Blum complexity measures, 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 May 09 '14 at 17:18
  • 2
    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 May 09 '14 at 17:21
  • @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 May 09 '14 at 17:26
  • @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 May 09 '14 at 17:45
  • @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 May 09 '14 at 19:13

2 Answers2

11

Quoting the complexity zoo:

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.

Community
  • 1
Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
  • 2
    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 May 10 '14 at 04:13
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

Florent Foucaud
  • 2,153
  • 12
  • 27