An Anthology of Complexity Assumptions In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue that we know very little about separations between complexity classes, and most results involve either using reasonable assumptions, or the random-oracle hypothesis. The most important and widely believed assumption is that PH does not collapse. In their words:


  In one approach, we assume as a working hypothesis that PH has infinitely many levels. Thus, any assumption which would imply that PH is finite is deemed incorrect. For example, Karp and Lipton showed that if NP ⊆ P/poly, then PH collapses to $\Sigma^P_2$. So, we believe that SAT does not have polynomial sized circuits. Similarly, we believe that the Turing-complete and many-one complete sets for NP are not sparse, because Mahaney showed that these conditions would collapse PH. One can even show that for any k ≥ 0, $P^{\mathrm{SAT}[k]} = P^{\mathrm{SAT}[k+1]}$ implies that PH is finite. Hence, we believe that $P^{\mathrm{SAT}[k]} \ne P^{\mathrm{SAT}[k+1]}$ for all k ≥ 0. Thus, if the polynomial hierarchy is indeed infinite, we can describe many aspects of the computational complexity of NP.


Apart from the assumption about PH not collapsing, there have been many other complexity assumptions. For instance:


Yao deems the following assumption plausible:
$RP \subseteq \bigcap\limits_{\epsilon &gt; 0} DTIME(2^{n^\epsilon})$.
Nisan and Wigderson make several assumptions related to derandomization.




The main idea of this question is what its title says: To be an anthology of complexity-theoretic assumptions. It would be great if the following conventions were adhered to (whenever possible):


The assumption itself;
The first paper in which the assumption is made;
Interesting results in which the assumption is used;
If the assumption has ever been refuted / proved, or whether its plausibility has ever been discussed.


This post is meant to be a community wiki; if an assumption is already cited, please edit the post and add new information rather than making a new post.



Edit (10/31/2011): Some cryptographic assumptions and information about them are listed in the following websites:


Wiki of Cryptographic Primitives and Hard Problems in Cryptography.
Helger Lipmaa's Cryptographic assumptions and hard problems.
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.