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

32

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

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

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

  1. Яо считает правдоподобным следующее предположение: .RPϵ>0DTIME(2nϵ)
  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. Криптографические предположения Хелгера Липмаа и трудные проблемы .
Sadeq Dousti
источник
2
Ницца. Дэвид Джонсон сделал что-то похожее для результатов сложности, используемых для демонстрации сложности аппроксимации в недавнем столбце
Суреш Венкат
@Suresh: ссылка на колонку Джонсона очень ценится.
MS Dousti
Требовать первую статью может быть сложно.
Андрас Саламон
@ Андрас: Да. По этой причине я добавил фразу «по возможности». Вы можете сослаться на статью, которую вы считаете первой. Поскольку это CW, если кто-то знает более старый результат, он просто исправляет сообщение.
MS Dousti
7
@Sadeq: www2.research.att.com/~dsj/columns/col25.pdf
Суреш Венкат

Ответы:

10
  • Предположение: Экспоненциальная гипотеза времени .
  • Впервые процитировано: « Будучи фольклором, оно было впервые оформлено в следующей статье: Рассел Импальяццо и Рамамохан Патури. 1999. Сложность k-SAT . В материалах четырнадцатой ежегодной конференции IEEE по вычислительной сложности ( COCO '99 ). IEEE Computer Society, Вашингтон, округ Колумбия, США, 237-240.
  • Использование (я): Предполагается, что никакая NP-полная задача не может быть решена за субэкспоненциальное время, и, следовательно, подразумевает, что P ≠ NP.
  • Статус: открыт.
неимоверный
источник
Я предполагаю, что ETH предполагает, что проблема 3-SAT не может быть решена в субэкспоненциальном времени. Ответы на этот пост ( cstheory.stackexchange.com/questions/3620/… ) подразумевают существование субэкспоненциальных алгоритмов времени для некоторых NP-полных задач, таких как Planar Independent Set.
Мухаммед Аль-Туркистани
Как пишет Мухаммед, описание в «Использовании (ях)» является неточным или просто неправильным.
Ёсио Окамото,
@YoshioOkamoto: это вики-сообщение сообщества. Почему бы не пойти дальше и сделать сообщение точным или даже исправить его?
MS Dousti
Я не уверен. Связанная страница википедии содержит больше информации, и мое редактирование будет просто повторением.
Ёсио Окамото
8
  • Предположение : NP не имеет p-меры 0
  • Впервые цитируется : Джек Х. Латц. Категория и мера в классах сложности . SIAM J. Comput. 19: 1100-1131, 1990.
  • μp(NP)0PNP
    1. Tpmp
    2. В NP есть пара непересекающихся языков, которые неразделимы с P [4];
    3. α<1nαttp
    4. mp
    5. NP содержит P-бииммунный язык [3];
    6. ENEEENEEEENEE

PNP

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

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

Джошуа Грохов
источник
Превосходно. Я полагаю, что вы можете проследить предположение к докторской диссертации Лутца 1987 года « Категория с ограничением по ресурсам и мера в классах экспоненциальной сложности » или к его статье IEEE 1987 года «Категория Бэра с ограниченными ресурсами и маленькие цепи в экспоненциальном пространстве» (которая недоступна в Интернете !).
MS Dousti
6
  • Предположение: NEEEE .
  • Впервые процитированы: Михир Белларе и Шафи Голдвассер. 1994. Сложность решения против поиска . SIAM J. Comput. 23, 1 (февраль 1994 г.), 97-119.
  • Использование (я): Если предположение выполняется, в NP существуют проблемы, поисковая версия которых (полиномиально) не сводит Cook-версию к своей версии решения. Другими словами, согласно данному предположению, не все языки в NP являются самосводимыми .
  • Статус: открыт.
Sadeq Dousti
источник