Entrada de blog de Scott Aaronson Los lógicos en safari tienen cinco datos que creo que la mayoría de las personas no conocen y que considerarían interesantes:
- Ahora sabemos que, si un extraterrestre con enormes poderes de cómputo viniera a la Tierra, podría demostrarnos si las blancas o las negras tienen la estrategia ganadora en el ajedrez. Para convencernos de la prueba, no tendríamos que confiar en el extraterrestre o su tecnología exótica, y no tendríamos que pasar miles de millones de años analizando una secuencia de movimientos tras otra. Simplemente tendríamos que entablar una breve conversación con el alienígena sobre las sumas de ciertos polinomios en campos finitos.
- Hay un conjunto de cajas finitas (y no inimaginablemente grandes), de modo que si supiéramos cómo empacar esas cajas en el maletero de su automóvil, también conoceremos una prueba de la Hipótesis de Riemann. De hecho, cada prueba formal de la hipótesis de Riemann con un máximo de (digamos) un millón de símbolos corresponde a alguna forma de empaquetar las cajas en su baúl, y viceversa. Además, una lista de las cajas y sus dimensiones se pueden escribir de manera factible.
- Suponiendo que usted prueba la Hipótesis de Riemann, es posible convencer a alguien de ese hecho, sin revelar nada más que el hecho de que usted lo probó . También es posible escribir la prueba de tal manera que otra persona pueda verificarla, con una confianza muy alta, habiendo visto solo 10 o 20 bits de la prueba.
- Si cada segundo, o así, la memoria de su computadora se limpiara completamente, excepto por los datos de entrada; el reloj; un programa estático, invariable; y un contador que solo podría establecerse en 1, 2, 3, 4 o 5, todavía sería posible (dado el tiempo suficiente) realizar un cálculo arbitrariamente largo, como si no se hubiera borrado la memoria. segundo. Es casi seguro que esto no sea cierto si el contador solo se pudiera establecer en 1, 2, 3 o 4. La razón por la que 5 es especial aquí es más o menos la misma razón por la que es especial en la prueba de Galois de la imposibilidad de solventar la ecuación quíntica.
- Sería genial probar que RSA es irrompible por las computadoras clásicas. ¡Pero cada técnica conocida para probar eso, si funcionara, daría simultáneamente un algoritmo para romper RSA! Por ejemplo, si demostró que RSA con una clave de n bits tomó n5 pasos para romper, habría descubierto un algoritmo para dividirlo en 2n ^ 1/5 pasos. Si demostró que RSA tomó 2n ^ 1/3 pasos para romper, habría descubierto un algoritmo para dividirlo en n (log n) ^ 2 pasos. A medida que demuestras que el problema es más difícil, al mismo tiempo lo demuestras para que sea más fácil.
Los comentarios en el sitio vinculado explican en detalle por qué son ciertos.