Существуют ли какие-либо известные проблемы NP, которые предположительно будут в среднем экспоненциально сложными?

12

ETH утверждает, что SAT не может быть решена в худшем случае за субэкспоненциальное время. Как насчет среднего случая? Есть ли естественные проблемы в NP, которые предположительно будут экспоненциально сложными в среднем случае?

Возьмите средний случай, чтобы означать среднее время работы с равномерным распределением на входах.

анонимное
источник
6
вам нужно определение «среднего случая», чтобы сделать ваш вопрос математически значимым.
Исинь Цао
2
vzn, я не понимаю актуальности вашего комментария. Я не спрашиваю об открытой проблеме здесь, очевидно, что нет проблем, о которых известно, что они в среднем тяжелые. Я спрашиваю, есть ли какие-либо кандидаты, которые, как предполагают, будут трудными в среднем случае. Пожалуйста, внимательно прочитайте вопрос, прежде чем комментировать.
Аноним
1
@vzn Точно! Я определенно согласен, мой смысл в том, что любой такой гипотезе кажется трудным сделать значимый шаг вперед или существенно изменить направления исследований, которые вы упомянули.
Усул
3
OP, обратите внимание, что ожидаемое время работы не AFAIK обычное количество, которое мы смотрим в среднем случае твердости. см. некоторый обзор теории сложности среднего случая Левина
Сашо Николова
1
Сашо Николов, я в курсе теории Левина. Однако существует также более простая сложность среднего случая, используемая для анализа поведения алгоритмов в конкретном распределении, начиная с [Karp 1986], который более распространен в алгоритмах. Я знаю, что проблема Tiling и несколько других проблем для DistNP завершены. Однако я не знаю, предположительно ли они будут в среднем экспоненциально сложными, используя простое значение среднего случая из-за Карпа.
Аноним

Ответы:

12

Можно предположить, что для обучения по паритету с проблемой шума (LPN) при постоянной частоте ошибок требуется время . Самый быстрый известный алгоритм (Блюм-Калай-Вассерман) использует время . 2 O ( n / log n )2n1o(1)2O(n/logn)

Райан О'Доннелл
источник
Спасибо. Не могли бы вы дать ссылки, где я могу прочитать больше о проблеме LPN?
Аноним
2
@ Аноним: В этой статье высказывается несколько предположений о твердости LPN: М. Алехнович. «Больше в среднем случае против сложности аппроксимации.» В учеб. 44-го Симпозиума по основам информатики, с. 298—307, 2003.
Юрий
Юрий, спасибо за ссылку: math.ias.edu/~misha/papers/average.ps
Аноним
11

Это не совсем то же самое, что и «каждый алгоритм», но в SODA'04 Ахлиопт Бим и Моллой предложили, чтобы для каждого алгоритма обратного отслеживания требовалось экспоненциальное время на случайных экземплярах 3SAT с переменными и предложениями , причем выбирается в диапазоне значений около порог удовлетворенности.с н сncnc

Дэвид Эппштейн
источник
Спасибо. Есть ли причина, по которой они не предполагают более сильное утверждение о том, что случайное k-SAT, ограниченное отношением предложений, близким к порогу выполнимости, экспоненциально сложно?
Аноним
4
Я предполагаю, что это потому, что они могут доказать результаты алгоритмов возврата, которые не зависят от P ≠ NP.
Дэвид Эппштейн
6

Существует несколько генераторов псевдослучайных чисел, у которых нет алгоритмов разбиения за полиномиальное время. Я думаю, вы могли бы считать их сложными в среднем случае. Проверьте генераторы на www.ecrypt.eu.org/stream/ Конечно, есть и другие, вы можете исследовать большинство из них онлайн.

Уильям Хирд
источник
Существует ли какой-либо конкретный многовидовой PRNG, который предположительно будет в среднем экспоненциально сложным?
Аноним
Генератор переменного шага, изобретенный Гюнтером, - это красота по нескольким причинам. Требуются два линейных регистра сдвига с обратной связью (LFSR) A & B и XOR на выходах, но тактирование двух регистров контролируется третьим LFSR (C), так что выходы A & B поступают в вентиль XOR нерегулярным образом. Поскольку биты C управляют только синхронизацией A & B и не появляются в выходном потоке, C можно рассматривать как квази скрытую переменную, которая нарушает внутреннюю линейность A & B. Это упрощенное объяснение, но вы захотите чтобы увидеть схему для себя.
Уильям Хирд
Я не знаком с «Генератором переменного шага, изобретенным Гюнтером». Предполагается, что это будет экспоненциально трудно в среднем?
Аноним
1
Я не знаю, как ответить на ваш комментарий, как изложено, но ASG считается неразрывной, если длина ключей для трех сдвиговых регистров составляет около 128 бит каждый. Если это равносильно тому, что в среднем «экспоненциально сложно», то я думаю, что ваш ответ - да.
Уильям Хирд
1
@Anonymous: Конечно, «голые» ASG можно усложнить, используя три ASG в качестве регистров AB & C для другой ASG, Гюнтер ссылается на это в своей оригинальной статье. Это как добавить больше раундов в блочный шифр. Как далеко можно увеличить твердость этим методом - открытый вопрос (и интересный) :-)
Уильям Хирд
0

Насколько я понимаю, в то время как есть некоторые кандидаты из теории неразрушимости криптографии и генераторов случайных чисел [например, некоторые цитируются в Razborov / Rudich, Natural Proofs], большинство аспектов вашего вопроса признаны экспертами как в основном ключевые «все еще открытые» вопросы в поле. от введения к всестороннему обзору, Средняя сложность случая Богданова и Тревизана (2006) есть некоторые связанные моменты. Также может быть полезна лекция Тревизана о результатах и ​​открытых вопросах средней сложности .







Правильные методы применения такой теории к естественным задачам и распределениям еще не найдены. С этой точки зрения текущее состояние теории сложности среднего случая в NP аналогично состоянию теории неприемлемости задач оптимизации NP до теоремы PCP.

ВЗН
источник
2
Не ответ на мой вопрос. Я думал, что объяснил вам, что я не ищу общих комментариев по смежным вопросам, я ищу кандидатские проблемы, которые, предположительно, будут сложными .
Аноним
1
без разницы! imho «теория не имеет существенного ответа на ваш вопрос на данный момент», наряду с некоторыми из лучших / ближайших полезных ссылок / авторитетов по Subj - это законный ответ на ваш вопрос, который был размещен не только для вас
vzn
1
@ Аноним, я все еще немного озадачен тем, что вы понимаете под «предположением». У всех нас могут быть наши личные предположения, поэтому неясно, ищите ли вы личное мнение, позицию по открытому вопросу, которую разделяют многие в исследованиях, или что-то среднее. Это может помочь дать более точное представление о том, что вы ищете. Кроме того, я считаю, что ответы, такие как vzn, являются поучительными и информативными, даже если они не имеют непосредственного отношения к вашему конкретному вопросу, поэтому я не вижу, что такие ответы следует так сильно обескураживать.
Усул
2
Если вы прочитали мой комментарий, на который ответил Питер Шор, я уже знаю о криптографических проблемах, которые предположительно являются суперполиномиально сложными. Пожалуйста, внимательно прочитайте вопрос, я не ищу суперполиномиально сложные проблемы, я ищу экспоненциально сложные.
Аноним
2
Пожалуйста, продолжайте обсуждение в чате.
Джефф