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

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

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

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

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

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

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

$\neq$

$\neq$

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