5
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    May 9 '14 at 16:55
  • $\begingroup$ "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). $\endgroup$
    – Bruno
    May 9 '14 at 17:18
  • 2
    $\begingroup$ 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. $\endgroup$ May 9 '14 at 17:21
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    May 9 '14 at 17:26
  • $\begingroup$ @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. $\endgroup$
    – Bruno
    May 9 '14 at 17:45
11
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.