Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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? –  Tim Oct 6 '12 at 22:39
    
@Tim: 1) The table in the Wikipedia article asserts nothing of the sort. 2) Yes, if you allow $c$ to vary. –  Qiaochu Yuan Oct 6 '12 at 22:47
    
(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$? –  Tim Oct 6 '12 at 22:51
    
@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. –  Qiaochu Yuan Oct 6 '12 at 22:53
    
THanks, about (1), I was messed up. –  Tim Oct 7 '12 at 2:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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