ETH afirma que SAT no se puede resolver en el peor de los casos en tiempo subexponencial. ¿Qué pasa con el caso promedio? ¿Hay problemas naturales en NP que se supone que son exponencialmente difíciles en el caso promedio?
Tome el caso promedio como el tiempo promedio de ejecución con una distribución uniforme en las entradas.
Respuestas:
fuente
fuente
Hay varios generadores de números psuedorandom que no tenemos algoritmos de tiempo polinomiales para romper. Supongo que podrías considerar que son difíciles en los casos promedio. Consulte los generadores en www.ecrypt.eu.org/stream/ Hay otros, por supuesto, puede investigar la mayoría de ellos en línea.
fuente
Tengo entendido que, si bien hay algunos candidatos de la teoría de la irrompibilidad de la criptografía y los generadores de números aleatorios [por ejemplo, algunos citados en Razborov / Rudich, Natural Proofs], los expertos reconocen la mayoría de los aspectos de su pregunta como preguntas clave "aún abiertas". en el campo. Desde la introducción de la encuesta integral, la complejidad de casos promedio de Bogdanov y Trevisan (2006) tiene algunos puntos relacionados. La conferencia de Trevisan en YouTube sobre hallazgos y preguntas abiertas sobre la complejidad promedio de los casos también puede ser útil.
fuente