Adversaires non uniformes vs uniformes

9

Cette question s'est posée dans le contexte de la cryptographie, mais je la présenterai ci-dessous en termes de théorie de la complexité, car les gens ici connaissent mieux cette dernière. Cette question est liée à des problèmes dans NP mais pas dans Average-P / poly et Beating Nonuniformity par Oracle Access .

Déclaration informelle: quand les adversaires non uniformes (c.-à-d. La famille de circuits de tailles multiples) réussissent-ils à briser un schéma cryptographique, mais les adversaires uniformes (c.-à-d. Les machines de Turing probabilistes à temps poly) ne le font pas?

Énoncé de complexité théorique: Ce n'est pas exactement la même chose que l'énoncé informel ci-dessus, mais je suis en fait intéressé par cette version:

Quels sont les problèmes naturels ?(NPP/poly)AvgP

En d'autres termes, quels problèmes naturels de N P durs en moyenne peuvent être résolus par une famille de circuits de plusieurs tailles?NP

Le mot résolu peut être interprété comme le cas le plus défavorable ou le cas moyen (ce dernier est préféré).

Si les problèmes naturels ne peuvent pas être trouvés facilement, les problèmes artificiels sont également acceptables.

MS Dousti
la source

Réponses:

14

Il n'y a pratiquement pas de problème naturel que l'on pense être en P / poly mais pas en P. Les exemples artificiels peuvent être adaptés pour répondre à votre question.

ENE1n

1length(X)

Luca Trevisan
la source