35
$\begingroup$

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.
$\endgroup$
5
  • 2
    $\begingroup$ Nice. David Johnson did something similar for complexity results used to show hardness of approximation in a recent column. $\endgroup$ Apr 8, 2011 at 21:48
  • $\begingroup$ @Suresh: A link to Johnson's column is much appreciated. $\endgroup$ Apr 8, 2011 at 21:55
  • $\begingroup$ Requiring the first paper might be tricky. $\endgroup$ Apr 8, 2011 at 22:01
  • $\begingroup$ @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. $\endgroup$ Apr 8, 2011 at 22:03
  • 7
    $\begingroup$ @Sadeq: www2.research.att.com/~dsj/columns/col25.pdf $\endgroup$ Apr 8, 2011 at 22:08

3 Answers 3

12
$\begingroup$
  • 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.
$\endgroup$
4
  • $\begingroup$ I guess ETH assumes that 3-SAT problem can not be decided in sub-exponential time. Answers to this post (cstheory.stackexchange.com/questions/3620/…) imply the existence of sub-exponential time algorithms for some NP-complete problems such as Planar Independent Set. $\endgroup$ Aug 2, 2011 at 12:55
  • $\begingroup$ As Mohammad writes, the description in "Use(s)" is imprecise or just wrong. $\endgroup$ Oct 31, 2011 at 15:29
  • $\begingroup$ @YoshioOkamoto: This is a community wiki post. Why not go ahead and make the post precise, or even correct it? $\endgroup$ Nov 2, 2011 at 9:19
  • $\begingroup$ I'm not sure. The linked wikipedia page contains more information, and my edit would just be a repetition. $\endgroup$ Nov 2, 2011 at 11:44
9
$\begingroup$
  • 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.

$\endgroup$
1
8
$\begingroup$
  • Assumption: NEEEE.
  • 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.
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.