Антология предположений о сложности

В статье «Гипотеза случайного оракула ложна» авторы (Чанг, Чор, Гольдрайх, Хартманис, Хостад, Ранджан и Рохатхи) обсуждают значение гипотезы о случайном оракуле . Они утверждают, что мы очень мало знаем о разделениях между классами сложности, и большинство результатов включают либо использование разумных допущений, либо гипотезу случайного оракула. Наиболее важным и широко распространенным предположением является то, что PH не разрушается. По их словам:

В одном подходе мы предполагаем в качестве рабочей гипотезы, что PH имеет бесконечно много уровней. Таким образом, любое предположение, которое подразумевает, что PH конечно, считается неверным. Например, Карп и Липтон показали, что если NP ⊆ P / poly, то PH падает до . Итак, мы считаем, что SAT не имеет схем полиномиального размера. Точно так же мы полагаем, что полные по Тьюрингу и много-единичные полные наборы для NP не редки, потому что Махани показал, что эти условия разрушат PH. Можно даже показать, что для любого k ≥ 0 из следует, что PH конечно. Следовательно, мы считаем, что$\Sigma^P_2$$P^{\mathrm{SAT}[k]} = P^{\mathrm{SAT}[k+1]}$$P^{\mathrm{SAT}[k]} \ne P^{\mathrm{SAT}[k+1]}$ для всех k ≥ 0. Таким образом, если полиномиальная иерархия действительно бесконечна, мы можем описать многие аспекты вычислительной сложности NP.

Помимо предположения о том, что PH не разрушается, было много других предположений о сложности. Например:

1. Яо считает правдоподобным следующее предположение: .$RP \subseteq \bigcap\limits_{\epsilon > 0} DTIME(2^{n^\epsilon})$
2. Нисан и Вигдерсон делают несколько предположений, касающихся дерандомизации.

Основная идея этого вопроса заключается в том, что написано в его названии: быть антологией теоретико-сложных предположений. Было бы замечательно, если бы следующие соглашения были соблюдены (когда это возможно):

1. Само предположение;
2. Первая статья, в которой сделано предположение;
3. Интересные результаты, в которых используется предположение;
4. Если предположение было когда-либо опровергнуто / доказано, или когда-либо обсуждалась его правдоподобность.

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.

Изменить (31.10.2011): Некоторые криптографические предположения и информация о них перечислены на следующих веб-сайтах:

1. Вики криптографических примитивов и сложные проблемы в криптографии .
2. Криптографические предположения Хелгера Липмаа и трудные проблемы .

• Предположение: Экспоненциальная гипотеза времени .
• Впервые процитировано: « Будучи фольклором, оно было впервые оформлено в следующей статье: Рассел Импальяццо и Рамамохан Патури. 1999. Сложность k-SAT . В материалах четырнадцатой ежегодной конференции IEEE по вычислительной сложности ( COCO '99 ). IEEE Computer Society, Вашингтон, округ Колумбия, США, 237-240.
• Использование (я): Предполагается, что никакая NP-полная задача не может быть решена за субэкспоненциальное время, и, следовательно, подразумевает, что P ≠ NP.
• Статус: открыт.

• Предположение : NP не имеет p-меры 0
• Впервые цитируется : Джек Х. Латц. Категория и мера в классах сложности . SIAM J. Comput. 19: 1100-1131, 1990.
• $\mu_p(NP) \neq 0$$P \neq NP$
  1. $\leq_T^p$$\leq_m^p$
  2. В NP есть пара непересекающихся языков, которые неразделимы с P [4];
  3. $\alpha < 1$$\leq_{n^{\alpha}-tt}^p$
  4. $\leq_m^p$
  5. NP содержит P-бииммунный язык [3];
  6. $E \neq NE$$EE \neq NEE$$EE \neq NEE$

$P \neq NP$

• Статус : открыт

[1] Дж. Лутц и Э. Майордомо. Кук против Карпа / Левина: разделяем понятия полноты, если NP не маленький . ТМФ. Комп. Sci. 164: 141-163, 1996.

[2] Д. Juedez и J. Lutz. Сложность и распределение сложных задач . SIAM J. Comput 24 (2): 279-295, 1995.

[3] Э. Майордомо. Почти каждый набор в экспоненциальном времени является P-би-иммунным . ТМФ. Комп. Sci. 136: 487-506, 1994.

[4] Л. Фортнов, Дж. Лутц и Э. Майордомо. Неотделимость и сильные гипотезы для непересекающихся пар NP . В Jean-Yves Marion и Thomas Schwentick, редакторы, Труды 27-го Симпозиума по теоретическим аспектам информатики, том 5 Международных научных трудов Лейбница по информатике (LIPIcs), стр. 395-404. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Германия, 2010.

• Предположение: NEE ≠ EE .
• Впервые процитированы: Михир Белларе и Шафи Голдвассер. 1994. Сложность решения против поиска . SIAM J. Comput. 23, 1 (февраль 1994 г.), 97-119.
• Использование (я): Если предположение выполняется, в NP существуют проблемы, поисковая версия которых (полиномиально) не сводит Cook-версию к своей версии решения. Другими словами, согласно данному предположению, не все языки в NP являются самосводимыми .
• Статус: открыт.