Проблемы в NP, но не в Average-P / poly

Теорема Карпа – Липтона утверждает, что если , то P H разрушается до Σ P 2 . Следовательно, при условии разделения между Σ P 2 и Σ P 3 , никакая N P -полная проблема не будет принадлежать P / p o l y .$\mathsf{NP} \subset \mathsf{P/poly}$$\mathsf{PH}$$\mathsf{\Sigma^P_2}$$\mathsf{\Sigma^P_2}$$\mathsf{\Sigma^P_3}$$\mathsf{NP}$$\mathsf{P/poly}$

Меня интересует следующий вопрос:

Предполагая, что не разрушается, или предполагая любые другие разумные допущения в отношении сложности конструкции, доказано , что трудно усредненные задачи N P не лежат в A v e r a g e - P / p o l y (если есть) )?$\mathsf{PH}$ $\mathsf{NP}$$\mathsf{Average\mbox{-}P/poly}$

Определение может быть найден в отношениях между среднем случае и в худшем случае сложности . Благодаря Tsuyoshi для указывая на то , что я на самом деле нужно использовать A V е г а г е - Р / р о л у вместо Р / р ö л у .$\mathsf{Average\mbox{-}P/poly}$$\mathsf{Average\mbox{-}P/poly}$$\mathsf{P/poly}$

Я думаю , существует проблемы , такие как (версии решения) ФАКТОРИНГА или DLoG , которые предполагаемые лежать в , но эта гипотеза не доказана на основе разделений между классы сложности. (Пожалуйста, поправьте меня, если я ошибаюсь.)$\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$

Это слегка улучшенная версия моих двух комментариев по данному вопросу вместе взятых.

Ограничим наше внимание проблемами распределения в DistNP (иначе (NP, P-computable)) для простоты. Тогда вы ищете проблему в DistNP ∖ Average-P / poly. Тавтологически такая проблема существует тогда и только тогда, когда DistNP ⊈ Average-P / poly. И если DistNP ⊈ Average-P / poly, то каждая проблема, связанная с DistNP, лежит за пределами Average-P / poly, потому что Average-P / poly закрывается при сокращениях среднего случая.

(Учитывая больший класс SampNP (иначе (NP, P-образец) ) вместо DistNP не сильно меняет ситуацию, потому что DistNP ⊆ Average-P / poly тогда и только тогда, когда SampNP ⊆ Average-P / poly. Эта эквивалентность является прямой следствие результата Импальяццо и Левина [IL90] о том, что каждая проблема распределения в SampNP сводится в среднем случае к некоторой проблеме распределения в DistNP.)

Я не знаю, какое естественное предположение подразумевает DistNP ⊈ Average-P / poly. Неизвестно, что предположение о том, что полиномиальная иерархия не разрушается, подразумевает даже более слабое следствие того, что DistNP ⊈ Average-P, согласно разделу 18.4 Arora и Barak [AB09]: «[…] даже если мы знаем, что если P = NP , тогда полиномиальная иерархия PH сводится к P […], у нас нет аналогичного результата для средней сложности случая ».

Ссылки

[AB09] Санджив Арора и Вооз Барак. Вычислительная сложность: современный подход , издательство Кембриджского университета, 2009.

[IL90] Рассел Импальяццо и Леонид А. Левин. Нет лучшего способа генерировать сложные экземпляры NP, чем равномерный случайный отбор. В 31-м ежегодном симпозиуме по основам компьютерных наук , 812–821, октябрь 1990 г. http://dx.doi.org/10.1109/FSCS.1990.89604