The complexity class QP consists of all problems that have quasi-polynomial time algorithms.
[1] An early example of a quasi-polynomial time algorithm was the Adleman–Pomerance–Rumely primality test.
For instance, this is true for the following problems: Other problems for which the best known algorithm takes quasi-polynomial time include: Problems for which a quasi-polynomial time algorithm has been announced but not fully published include: Quasi-polynomial time has also been used to study approximation algorithms.
Problems with a QPTAS include minimum-weight triangulation,[15] finding the maximum clique on the intersection graph of disks,[16] and determining the probability that a hypergraph becomes disconnected when some of its edges fail with given independent probabilities.
[17] More strongly, the problem of finding an approximate Nash equilibrium has a QPTAS, but cannot have a PTAS under the exponential time hypothesis.