<ul>
<li><strong>Assumption:</strong> <a href="http://en.wikipedia.org/wiki/Exponential_time_hypothesis">Exponential time hypothesis</a>.</li>
<li><strong>First cited in:</strong> While being folklore, it was first formalized in the following paper: Russell Impagliazzo and Ramamohan Paturi. 1999. <a href="http://dx.doi.org/10.1109%2FCCC.1999.766282">The Complexity of k-SAT</a>. In <em>Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity</em> (<em>COCO '99</em>). IEEE Computer Society, Washington, DC, USA, 237-240.</li>
<li><strong>Use(s):</strong> It assumes that no NP-complete problem can be decided in sub-exponential time, and therefore implies that P ≠ NP.</li>
<li><strong>Status:</strong> Open.</li>
</ul>

CC BY-SA 3.0
2011-08-02T12:55:02.810Z
I guess ETH assumes that 3-SAT problem can not be decided in sub-exponential time. Answers to this post (http://cstheory.stackexchange.com/questions/3620/subexponentially-solvable-hard-graph-problems) imply the existence of sub-exponential time algorithms for some NP-complete problems such as Planar Independent Set.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-10-31T15:29:41.883Z
As Mohammad writes, the description in "Use(s)" is imprecise or just wrong.
Yoshio Okamoto
CC BY-SA 3.0
2011-11-02T09:19:57.143Z
@YoshioOkamoto: This is a community wiki post. Why not go ahead and make the post precise, or even correct it?
Sadeq Dousti
CC BY-SA 3.0
2011-11-02T11:44:55.663Z
I'm not sure.  The linked wikipedia page contains more information, and my edit would just be a repetition.
Yoshio Okamoto
CC BY-SA 3.0
2011-04-14T12:30:55.767Z
2011-04-14T12:30:55.767Z
Incredible
<ul>
<li><strong>Assumption</strong>: NP does not have p-measure 0</li>
<li><strong>First cited in</strong>: Jack H. Lutz. <a href="http://dx.doi.org/10.1137/0219076" rel="nofollow noreferrer">Category and measure in complexity classes</a>. SIAM J. Comput. 19:1100-1131, 1990. </li>
<li><strong>Use(s)</strong>: If $\mu_p(NP) \neq 0$ then $P \neq NP$ and: 

<ol>
<li>There is a language that is $\leq_T^p$-complete for NP but not $\leq_m^p$-complete for NP [1];</li>
<li>There is a pair of disjoint languages in NP that are P-inseparable [4];</li>
<li>For every $\alpha &lt; 1$, every $\leq_{n^{\alpha}-tt}^p$-hard language for NP is dense [3];</li>
<li>Every $\leq_m^p$-complete language for NP has a dense exponential complexity core [2];</li>
<li>NP contains a P-bi-immune language [3]; </li>
<li>$E \neq NE$ and $EE \neq NEE$ ([1] - see <a href="https://cstheory.stackexchange.com/questions/5961/an-anthology-of-complexity-assumptions/6059#6059">this answer</a> for more consequences of $EE \neq NEE$).</li>
</ol></li>
</ul>

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

<ul>
<li><strong>Status</strong>: Open</li>
</ul>

<p>[1] J. Lutz and E. Mayordomo. <a href="http://dx.doi.org/10.1016/0304-3975(95)00189-1" rel="nofollow noreferrer">Cook versus Karp/Levin: separating completeness notions if NP is not small</a>. Theoret. Comp. Sci. 164:141-163, 1996. </p>

<p>[2] D. Juedez and J. Lutz. <a href="http://dx.doi.org/10.1137/S0097539792238133" rel="nofollow noreferrer">The complexity and distribution of hard problems</a>. SIAM J. Comput 24(2):279-295, 1995.</p>

<p>[3] E. Mayordomo. <a href="http://dx.doi.org/10.1016/0304-3975(94)00023-C" rel="nofollow noreferrer">Almost every set in exponential time is P-bi-immune</a>. Theoret. Comp. Sci. 136:487-506, 1994.</p>

<p>[4] L. Fortnow, J. Lutz, and E. Mayordomo. <a href="http://www.cs.uchicago.edu/~fortnow/papers/insep.pdf" rel="nofollow noreferrer">Inseparability and strong hypotheses for disjoint NP pairs</a>. 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.</p>

CC BY-SA 3.0
2011-04-17T05:34:51.303Z
Excellent. I believe you can track down the assumption to Lutz's 1987 PhD thesis "[Resource-Bounded Category and Measure in Exponential Complexity Classes](http://caltechcstr.library.caltech.edu/346/01/5243_TR_87.pdf)" or to his 1987 IEEE paper "resource-bounded Baire category and small circuits in exponential space" (which is not available online!).
Sadeq Dousti
CC BY-SA 3.0
2011-04-16T19:03:49.007Z
2011-04-16T19:03:49.007Z
2017-04-13T12:32:28.743Z
Joshua Grochow
<ul>
<li><strong>Assumption:</strong> <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nee" rel="nofollow">NEE</a> ≠ <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#ee" rel="nofollow">EE</a>.</li>
<li><strong>First cited in:</strong> Mihir Bellare and Shafi Goldwasser. 1994. <a href="http://dx.doi.org/10.1137/S0097539792228289" rel="nofollow">The Complexity of Decision Versus Search</a>. SIAM J. Comput. 23, 1 (February 1994), 97-119.</li>
<li><strong>Use(s):</strong> 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 <a href="http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l2.ps" rel="nofollow">self reducible</a>.</li>
<li><strong>Status:</strong> Open.</li>
</ul>

CC BY-SA 3.0
2011-04-13T21:47:12.643Z
2015-09-01T18:22:54.913Z
2015-09-01T18:22:54.913Z
Sadeq Dousti
<p>In the paper <a href="http://dx.doi.org/10.1016/S0022-0000%2805%2980084-4">The Random Oracle Hypothesis Is False</a>, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the <strong>random-oracle hypothesis</strong>. They argue that we know very little about separations between complexity classes, and most results involve either using <em>reasonable</em> assumptions, or the random-oracle hypothesis. The most important and widely believed assumption is that PH does not collapse. In their words:</p>

<blockquote>
  <p>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, <a href="http://dx.doi.org/10.1145/800141.804678">Karp and Lipton</a> 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 <a href="http://dx.doi.org/10.1016/0022-0000%2882%2990002-2">Mahaney</a> showed that these conditions would collapse PH. One can even <a href="http://dx.doi.org/10.1137/0204037">show that</a> 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.</p>
</blockquote>

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

<ol>
<li><a href="http://dx.doi.org/10.1109/SFCS.1982.95">Yao</a> deems the following assumption plausible:
$RP \subseteq \bigcap\limits_{\epsilon &gt; 0} DTIME(2^{n^\epsilon})$.</li>
<li><a href="http://dx.doi.org/10.1016/S0022-0000%2805%2980043-1">Nisan and Wigderson</a> make several assumptions related to derandomization.</li>
</ol>

<hr>

<p>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):</p>

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

<p><code>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.</code></p>

<hr>

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

<ol>
<li>Wiki of <a href="http://www.ecrypt.eu.org/wiki/index.php/Main_Page">Cryptographic Primitives and Hard Problems in Cryptography</a>.</li>
<li>Helger Lipmaa's <a href="http://www.cs.ut.ee/~lipmaa/crypto/link/public/assumptions.php">Cryptographic assumptions and hard problems</a>.</li>
</ol>

CC BY-SA 3.0
2011-04-08T21:48:24.807Z
Nice. David Johnson did something similar for complexity results used to show hardness of approximation in a recent column.
Suresh Venkat
CC BY-SA 3.0
2011-04-08T21:55:45.667Z
@Suresh: A link to Johnson's column is much appreciated.
Sadeq Dousti
CC BY-SA 3.0
2011-04-08T22:01:01.140Z
Requiring the _first_ paper might be tricky.
András Salamon
CC BY-SA 3.0
2011-04-08T22:03:47.920Z
@András: Yes. For that reason, I added the "whenever possible" phrase. You can cite the paper *you* think is the first one. Since this is CW, if anyone knows an older result, (s)he simply corrects the post.
Sadeq Dousti
CC BY-SA 3.0
2011-04-08T22:08:16.513Z
@Sadeq: http://www2.research.att.com/~dsj/columns/col25.pdf
Suresh Venkat
<cc.complexity-theory><complexity-classes><big-list><complexity-assumptions>
An Anthology of Complexity Assumptions
Sadeq Dousti
# An Anthology of Complexity Assumptions

(Asked by: username_0 on 2011-04-08)

In the paper [The Random Oracle Hypothesis Is False](http://dx.doi.org/10.1016/S0022-0000%2805%2980084-4), 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](http://dx.doi.org/10.1145/800141.804678) 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](http://dx.doi.org/10.1016/0022-0000%2882%2990002-2) showed that these conditions would collapse PH. One can even [show that](http://dx.doi.org/10.1137/0204037) 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](http://dx.doi.org/10.1109/SFCS.1982.95) deems the following assumption plausible:
   $RP \subseteq \bigcap\limits\_{\epsilon > 0} DTIME(2^{n^\epsilon})$.
2. [Nisan and Wigderson](http://dx.doi.org/10.1016/S0022-0000%2805%2980043-1) 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](http://www.ecrypt.eu.org/wiki/index.php/Main_Page).
2. Helger Lipmaa's [Cryptographic assumptions and hard problems](http://www.cs.ut.ee/~lipmaa/crypto/link/public/assumptions.php).

**Tags:** cc.complexity-theory, complexity-classes, big-list, complexity-assumptions
> **Comments:**
> **username_1**: Nice. David Johnson did something similar for complexity results used to show hardness of approximation in a recent column.  
> **username_0**: @Suresh: A link to Johnson's column is much appreciated.  
> **username_2**: Requiring the _first_ paper might be tricky.  
> **username_0**: @András: Yes. For that reason, I added the "whenever possible" phrase. You can cite the paper *you* think is the first one. Since this is CW, if anyone knows an older result, (s)he simply corrects the post.  
> **username_1**: @Sadeq: http://www2.research.att.com/~dsj/columns/col25.pdf  

---

## 3 answers

### Answer by username_3 on 2011-04-14. Score: 11

* **Assumption:** [Exponential time hypothesis](http://en.wikipedia.org/wiki/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](http://dx.doi.org/10.1109%2FCCC.1999.766282). 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.

> **Comments:**
> **username_4**: I guess ETH assumes that 3-SAT problem can not be decided in sub-exponential time. Answers to this post (http://cstheory.stackexchange.com/questions/3620/subexponentially-solvable-hard-graph-problems) imply the existence of sub-exponential time algorithms for some NP-complete problems such as Planar Independent Set.  
> **username_5**: As Mohammad writes, the description in "Use(s)" is imprecise or just wrong.  
> **username_0**: @YoshioOkamoto: This is a community wiki post. Why not go ahead and make the post precise, or even correct it?  
> **username_5**: I'm not sure.  The linked wikipedia page contains more information, and my edit would just be a repetition.  

---

### Answer by username_6 on 2011-04-16. Score: 10

* **Assumption**: NP does not have p-measure 0
* **First cited in**: Jack H. Lutz. [Category and measure in complexity classes](http://dx.doi.org/10.1137/0219076). 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](https://cstheory.stackexchange.com/questions/5961/an-anthology-of-complexity-assumptions/6059#6059) 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](http://dx.doi.org/10.1016/0304-3975(95)00189-1). Theoret. Comp. Sci. 164:141-163, 1996.

[2] D. Juedez and J. Lutz. [The complexity and distribution of hard problems](http://dx.doi.org/10.1137/S0097539792238133). SIAM J. Comput 24(2):279-295, 1995.

[3] E. Mayordomo. [Almost every set in exponential time is P-bi-immune](http://dx.doi.org/10.1016/0304-3975(94)00023-C). Theoret. Comp. Sci. 136:487-506, 1994.

[4] L. Fortnow, J. Lutz, and E. Mayordomo. [Inseparability and strong hypotheses for disjoint NP pairs](http://www.cs.uchicago.edu/~fortnow/papers/insep.pdf). 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.

> **Comments:**
> **username_0**: Excellent. I believe you can track down the assumption to Lutz's 1987 PhD thesis "[Resource-Bounded Category and Measure in Exponential Complexity Classes](http://caltechcstr.library.caltech.edu/346/01/5243_TR_87.pdf)" or to his 1987 IEEE paper "resource-bounded Baire category and small circuits in exponential space" (which is not available online!).  

---

### Answer by username_0 on 2011-04-13. Score: 8

* **Assumption:** [NEE](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nee) ≠ [EE](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#ee).
* **First cited in:** Mihir Bellare and Shafi Goldwasser. 1994. [The Complexity of Decision Versus Search](http://dx.doi.org/10.1137/S0097539792228289). 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](http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l2.ps).
* **Status:** Open.


---

