An Anthology of Complexity Assumptions
Assumption: Exponential time hypothesis.
First cited in: While being folklore, it was first formalized in the following paper: Russell Impagliazzo and Ramamohan Paturi. 1999. The Complexity of k-SAT. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 237-240.
Use(s): It assumes that no NP-complete problem can be decided in sub-exponential time, and therefore implies that P ≠ NP.
Status: Open.