1
$\begingroup$
  1. From Wikipedia

    Quasi-polynomial time algorithms are algorithms which run slower than polynomial time, yet not so slow as to be exponential time. The worst case running time of a quasi-polynomial time algorithm is $2^{O((\log n)^c)}$ for some fixed $c$.

    • I found in an earlier table on the same page, quasi-polynomial means $2poly(\log n)$. Can I suppose the two definitions are the same?

    • I was wondering if quasi-polynomial time algorithms should run faster than polynomial time, yet not so fast as to be exponential time instead?

  2. From Wikipedia

    In mathematics, a quasi-polynomial (pseudo-polynomial) is a generalization of polynomials. While the coefficients of a polynomial come from a ring, the coefficients of quasi-polynomials are instead periodic functions with integral period. A quasi-polynomial can be written as $q(k) = c_d(k) k^d + c_{d-1}(k) k^{d-1} + \cdots + c_0(k)$, where $c_{i}(k)$ is a periodic function with integral period.

    Is quasi-polynomial time complexity for algorithms not related to this mathematical quasi-polynomial concept?

Thanks!

1 Answers 1

1

No, they're not related. They're just both things which aren't polynomials but which are kind of like polynomials. (Personally I think they are both bad pieces of terminology.)

"Faster than polynomial time, yet not so fast as to be exponential time" doesn't make sense. Exponential time is slower than polynomial time.

  • 0
    Thanks, Qiaochu! (1) "Exponential time is slower than polynomial time", but I saw the opposite is true in the table of the same Wikipedia article. (2) Do the two different definitions of quasi-polynomial complexity, i.e. $2O((\log n)^c)$ for some fixed $c$ (I guess $c>0$) and $2 \text{poly}(\log n)$, mean the same?2012-10-06
  • 0
    @Tim: 1) The table in the Wikipedia article asserts nothing of the sort. 2) Yes, if you allow $c$ to vary.2012-10-06
  • 0
    (1) What I wanted to say is that exponential time complexity grows faster than polynomial time complexity. If I understand correctly, the table lists different types of complexity from slow to fast growing, although it doesn't explicitly say so. (2) For the two definitions to be same, is it require that $c\geq 1$ or $c>0$?2012-10-06
  • 0
    @Tim: 1) That is not what "run faster" means. "Run faster" means "takes less time to run." 2) If you want "quasi-polynomial" to mean "strictly faster than polynomial," you want $c > 1$. Again, I think that "quasi-polynomial" is bad terminology, and if you ever actually want to talk about "quasi-polynomial" time algorithms, you should clarify exactly what you mean by that.2012-10-06