一千萬個為什麽

搜索

復雜假設的選集

在論文隨機Oracle假設是假的中,作者(Chang,Chor,Goldreich) ,Hartmanis,Håstad,Ranjan和Rohatgi)討論隨機預言假設的含義。他們認為我們對復雜性類之間的分離知之甚少,而且大多數結果都涉及使用合理的假設或隨機預言假設。最重要和最廣泛認為的假設是PH不會崩潰。用他們的話說:

在一種方法中,我們假設PH具有無限多個級別的工作假設。因此,任何暗示PH有限的假設都被認為是不正確的。例如, Karp和Lipton 顯示,如果NP⊆P/ poly,那麽PH將折疊為$ \ Sigma ^ P_2 $。因此,我們認為SAT沒有多項式大小的電路。同樣,我們認為NP的圖靈完備和多套完整集並不稀疏,因為 Mahaney 表明這些情況會使PH崩潰。甚至可以顯示任何k≥0,$ P ^ {\ mathrm {SAT} [k]} = P ^ {\ mathrm {SAT} [k + 1]} $暗示PH是有限的。因此,我們認為,對於所有k≥0,$ P ^ {\ mathrm {SAT} [k]} \ ne P ^ {\ mathrm {SAT} [k + 1]} $。因此,如果多項式層次確實是無窮大的,我們可以描述NP的計算復雜性的許多方面。

除了關於PH沒有崩潰的假設之外,還有許多其他復雜性假設。例如:

  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.

轉載註明原文: 復雜假設的選集