Неравные против единообразных противников

9

Этот вопрос возник в контексте криптографии, но ниже я представлю его с точки зрения теории сложности, поскольку здесь люди больше знакомы с последним. Этот вопрос связан с проблемами в NP, но не в Average-P / poly и неоднородности биения по Oracle Access .

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

Теоретическая сложность: это не совсем то же самое, что и вышеприведенное неофициальное утверждение, но на самом деле меня интересует эта версия:

В чем заключаются естественные проблемы (NPP/poly)AvgP ?

Другими словами, что трудно в среднем естественноNPпроблемы можно решить с помощью многомерного семейства микросхем?

Слово « решено» можно интерпретировать как наихудший или средний случай (последний вариант является предпочтительным).

Если естественные проблемы не могут быть легко найдены, искусственные проблемы также приемлемы.

М.С. Дусти
источник

Ответы:

14

Вряд ли существует какая-либо естественная проблема, которая, как полагают, связана с P / poly, но не с P. Искусственные примеры можно адаптировать для ответа на ваш вопрос.

Предполагать ENE, то есть унарный язык L в NP, которого нет в P - унарный означает, что все строки в языке имеют вид 1n для некоторых п.

Затем определим L 'как множество всех строк x, таких что 1length(x) находится в L. Это в NP, это в P / poly, и это не в среднем полиномиальном времени

Лука Тревизан
источник