Editing Time complexity (section)

=== 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.