# 復雜假設的選集

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.

1. 假設本身;
2. 作出假設的第一篇論文;
3. 使用假設的有趣結果;
4. 如果這個假設曾經被駁斥/證明，或者是否曾經討論過它的合理性。

這篇文章是一個社區維基;如果已經引用了一個假設，請編輯帖子並添加新信息，而不是發布新帖子。

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

1. 加密基元和密碼學中的難題的Wiki。
2. Helger Lipmaa的加密假設和難題

## 最佳答案

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