|
|
|
|
|
|
by anuragbiyani
3844 days ago
|
|
|
A 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. |
|
|