Supongamos que tiene una función que es difícil de calcular con pequeños circuitos (es decir, si intenta resolverla con pequeños circuitos, siempre obtendrá algunas entradas incorrectas, pero podría obtener diferentes entradas incorrectas si intenta con diferentes circuitos).
Podría haber dos explicaciones a priori: (1) las “entradas duras” se distribuyen entre todas las entradas, o (2) hay un pequeño conjunto de entradas que son “muy duras” (en el sentido de que no hay un circuito pequeño incluso puede esperar obtener la mitad de ellos correctamente) y el resto de las entradas pueden ser fáciles.
El lema hardcore de Impagliazzo muestra que (2) es siempre el caso. Esto es útil en particular debido a sus aplicaciones en el peor de los casos y la complejidad del caso promedio. En particular, si tiene una función que es difícil en el peor de los casos (cada circuito pequeño que intenta calcularlo tiene uno o dos errores, por ejemplo), puede usar el lema de Impagliazzo como parte clave de una larga cadena de resultados para obtener funciones que son difíciles en promedio (en el sentido de que un circuito pequeño tendrá mal la mitad de todas las entradas).
- ¿Por qué los estudiantes que se especializan en matemáticas, física, informática y estadística no se gustan?
- Tengo 28 años, estoy desempleado, tengo 17 meses de tiempo libre y quiero ser Red Topcoder para el final. Si es posible, ¿cómo debo hacerlo?
- ¿Existe algún software GRATUITO que pueda aumentar mi calidad o aptitud de inteligencia?
- ¿Dónde y cómo se superponen la programación y las matemáticas?
- ¿Podemos aplicar el aprendizaje automático en cualquier idioma o hay algo específico que sirva para ese propósito? ¿Cuáles son los modelos matemáticos efectivos utilizados principalmente en ML?
Incluso puede llevar estas ideas más allá para mostrar: si hay una función difícil en el peor de los casos para circuitos pequeños, entonces P = BPP. El lema hardcore es un ingrediente clave en esto.
