Assuming that *P* ≠ *NP, NP-*complete problems can not be solved in polynomial time. On the other hand, they can (trivially) be solved in exponential time. A natural question is therefore: Can we solve (some) *NP*-complete problems in *sub-exponential time*? For example, if the trivial time bound is *O*(2^{n}), can we reduce it to, say, *O*(2^{√}* ^{n}*) or at least

*O*(2

^{n/log log n })? There is some evidence that this might be impossible, at least for certain types of problems. The notion of sub-exponential time, however, has to be interpreted with some care below.

If the best we can hope for are exponential running times of order $O(α^{n}), then what is the best possible (smallest) value of α? Questions of this type have seen increasing interest during the last years. For example, the well-known 3-colorability problem (decide whether a graph can be colored with 3 colors) can trivially be solved in time *O*(3^{n}), where *n* is the number of vertices. In a series of papers this has been brought down to *O*(1.3289^{n}). The proposed project primarily aims at developing fast exponential time algorithms in this sense. Such algorithms are also known as *exact algorithms* (as opposed to approximation algorithms for solving *NP*-hard problems). There are numerous interesting open problems mostly related to certain ``threshold'' values for α.