5 ms·
Is somebody able to explain in more detail what the "Greater metropolitan area" of P space means? I have a CS undergrad degree so I get what polynomial space is
by LesZedCB 11y ago
Is somebody able to explain in more detail what the "Greater metropolitan area" of P space means? I have a CS undergrad degree so I get what polynomial space is, just not sure about the quasi-p-space part.
- apetresc 11y agoQuasi-polynomial time is slower than polynomial time, but (much) faster than exponential time. Basically, if polynomial is O(n^c) and exponential is O(c^n), then quasi-polynomial is O(x^(log(n)^c); that is, n does show up in the exponent, but it's some power of the log of n. In theoretical terms, it's much closer to a polynomial problem than an exponential one.
- LesZedCB 11y agoGotcha, that makes perfect sense, thanks for the explanation!
- anuragbiyani 11y agoA quasi-polynomial time algorithm is one which has a worst case running time of 2^[O((log n)^c)], for some fixed constant 'c'. Polynomial time (PTIME) algorithms are a special case (where c=1). "Greater metropolitan area" is a way of saying that Babai's proposed algorithm while not exactly in PTIME, is still very close. Indeed, in a certain sense it is now "closer" to PTIME than EXPTIME.
- LesZedCB 11y agoThanks!