Esta pregunta surgió en el contexto de la criptografía, pero a continuación la presentaré en términos de teoría de la complejidad, ya que las personas aquí están más familiarizadas con esta última. Esta pregunta está relacionada con problemas en NP pero no en Promedio-P / poli y No uniformidad de latido por Oracle Access .
Declaración informal: ¿ Cuándo los adversarios no uniformes (es decir, la familia de circuitos de tamaño polivinílico) logran romper un esquema criptográfico, pero los adversarios uniformes (es decir, las máquinas Turing probabilísticas de tiempo polivinílico) no lo hacen?
Enunciado teórico de la complejidad: esto no es exactamente lo mismo que el enunciado informal anterior, pero en realidad estoy interesado en esta versión:
¿Qué problemas naturales se encuentran en ?
En otras palabras, ¿qué problemas naturales difíciles de resolver pueden ser resueltos por una familia de circuitos de tamaño polivinílico?
La palabra resuelta se puede interpretar como el peor de los casos o el caso promedio (se prefiere este último).
Si los problemas naturales no se pueden encontrar fácilmente, los problemas artificiales también son aceptables.