An Anthology of Complexity Assumptions

Question

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:

1. Yao deems the following assumption plausible: $RP \subseteq \bigcap\limits_{\epsilon > 0} DTIME(2^{n^\epsilon})$.
2. 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):

1. The assumption itself;
2. The first paper in which the assumption is made;
3. Interesting results in which the assumption is used;
4. 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:

1. Wiki of Cryptographic Primitives and Hard Problems in Cryptography.
2. Helger Lipmaa's Cryptographic assumptions and hard problems.

Answer 1

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

Answer 2

• Assumption: NP does not have p-measure 0
• First cited in: Jack H. Lutz. Category and measure in complexity classes. SIAM J. Comput. 19:1100-1131, 1990.
• Use(s): If $\mu_p(NP) \neq 0$ then $P \neq NP$ and:
  1. There is a language that is $\leq_T^p$-complete for NP but not $\leq_m^p$-complete for NP [1];
  2. There is a pair of disjoint languages in NP that are P-inseparable [4];
  3. For every $\alpha < 1$, every $\leq_{n^{\alpha}-tt}^p$-hard language for NP is dense [3];
  4. Every $\leq_m^p$-complete language for NP has a dense exponential complexity core [2];
  5. NP contains a P-bi-immune language [3];
  6. $E \neq NE$ and $EE \neq NEE$ ([1] - see this answer for more consequences of $EE \neq NEE$).

As far as I know, the above consequences are not known to follow merely from the assumption that $P \neq NP$.

• Status: Open

[1] J. Lutz and E. Mayordomo. Cook versus Karp/Levin: separating completeness notions if NP is not small. Theoret. Comp. Sci. 164:141-163, 1996.

[2] D. Juedez and J. Lutz. The complexity and distribution of hard problems. SIAM J. Comput 24(2):279-295, 1995.

[3] E. Mayordomo. Almost every set in exponential time is P-bi-immune. Theoret. Comp. Sci. 136:487-506, 1994.

[4] L. Fortnow, J. Lutz, and E. Mayordomo. Inseparability and strong hypotheses for disjoint NP pairs. In Jean-Yves Marion and Thomas Schwentick, editors, Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 395-404. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2010.

Answer 3

• Assumption: NEE ≠ EE.
• First cited in: Mihir Bellare and Shafi Goldwasser. 1994. The Complexity of Decision Versus Search. SIAM J. Comput. 23, 1 (February 1994), 97-119.
• Use(s): If the assumption holds, there exist problems in NP whose search version does not (polynomially) Cook-reduce to their decision version. In other words, under the given assumption, not all languages in NP are self reducible.
• Status: Open.