2
$\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

2

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
    @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