Editing Time complexity (section)

== Quasi-polynomial time ==
{{main|Quasi-polynomial time}}
'''Quasi-polynomial time''' algorithms are algorithms whose running time exhibits [[quasi-polynomial growth]], a type of behavior that may be slower than polynomial time but yet is significantly faster than [[exponential time]]. The worst case running time of a quasi-polynomial time algorithm is <math>2^{O(\log^c n)}</math> for some fixed {{nowrap|<math>c > 0</math>.}} When <math>c=1</math> this gives polynomial time, and for <math>c < 1</math> it gives sub-linear time.

There are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed [[Steiner tree problem]], for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of <math>O(\log^3 n)</math> (''n'' being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.

Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include the [[planted clique]] problem in which the goal is to [[clique problem|find a large clique]] in the union of a clique and a [[random graph]]. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a [[computational hardness assumption]] to prove the difficulty of several other problems in computational [[game theory]], [[property testing]], and [[machine learning]].<ref>{{cite conference | last1 = Braverman | first1 = Mark | author1-link = Mark Braverman (mathematician) | last2 = Kun-Ko | first2 = Young | last3 = Rubinstein | first3 = Aviad | last4 = Weinstein | first4 = Omri | editor-last = Klein | editor-first = Philip N. | arxiv = 1504.08352 | contribution = ETH hardness for densest-{{mvar|k}}-subgraph with perfect completeness | doi = 10.1137/1.9781611974782.86 | mr = 3627815 | pages = 1326–1341 | publisher = Society for Industrial and Applied Mathematics | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 | year = 2017| isbn = 978-1-61197-478-2 }}</ref>

The complexity class '''QP''' consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of [[DTIME]] as follows.<ref>{{ComplexityZoo|Class QP: Quasipolynomial-Time|Q#qp}}</ref>
:<math>\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME} \left(2^{\log^c n}\right)</math>

=== Relation to NP-complete problems ===

In complexity theory, the unsolved [[P versus NP]] problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for [[NP-complete]] problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is the square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the [[exponential time hypothesis]].<ref name="ETH">{{cite journal | last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo | last2 = Paturi | first2 = Ramamohan | doi = 10.1006/jcss.2000.1727 | issue = 2 | journal = [[Journal of Computer and System Sciences]] | mr = 1820597 | pages = 367–375 | title = On the complexity of {{mvar|k}}-SAT | url = https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf | volume = 62 | year = 2001| doi-access = free }}</ref> Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of [[approximation algorithms]] make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the [[set cover]] problem.