Этот вопрос возник в контексте криптографии, но ниже я представлю его с точки зрения теории сложности, поскольку здесь люди больше знакомы с последним. Этот вопрос связан с проблемами в NP, но не в Average-P / poly и неоднородности биения по Oracle Access .
Неформальное утверждение: когда неоднородные противники (то есть многоконтурное семейство цепей) преуспевают в взломе криптографической схемы, а единообразные противники (то есть вероятностные многовременные машины Тьюринга) - нет?
Теоретическая сложность: это не совсем то же самое, что и вышеприведенное неофициальное утверждение, но на самом деле меня интересует эта версия:
В чем заключаются естественные проблемы ?
Другими словами, что трудно в среднем естественнопроблемы можно решить с помощью многомерного семейства микросхем?
Слово « решено» можно интерпретировать как наихудший или средний случай (последний вариант является предпочтительным).
Если естественные проблемы не могут быть легко найдены, искусственные проблемы также приемлемы.