¿Cuáles son las mejores pruebas en informática?

Answer 1

Aquí están los primeros que vinieron a la mente sin ningún orden en particular. No tengo un fuerte presentimiento sobre esto. No consideré cuidadosamente todas las alternativas 🙂

1. La indecidibilidad del problema de detención. (Turing)
2. Indecidibilidad de la igualdad en las CFL. (Arroz-Greibach)
3. Minimización de máquinas de estados finitos en [matemáticas] O (n log n) [/ matemáticas] (Myhill-Nerode-Hopcroft)
4. Simulando el espacio no determinista [matemático] F (n) [/ matemático] en el espacio determinista [matemático] F ^ 2 (n) [/ matemático]. (Savitch)
5. Análisis lineal de tiempo de gramáticas LR (Earley)
6. Prueba de planaridad de tiempo lineal. (Tarjan)
7. Algoritmo de transformación rápida de Fourier (Gauss-Cooley-Tukey)
8. Algoritmo de Kadane para subarrays de suma máxima (Kadane)
9. La satisfacción es NP-completa (Cook-Levin)
10. Criptografía de clave pública (Euclid-Fermat-Rivest-Shamir-Adelman)

Cada algoritmo necesita una prueba de corrección. Ahora las pruebas no son tan interesantes, pero los algoritmos son … tantas opciones 🙂

Agregué dos más para hacer un par de diez, junto con las atribuciones que espero sean correctas. Por favor corrija si me equivoqué.

Answer 2

¡Hay demasiados buenos! Soy bastante aficionado a las pruebas de la integridad de Turing de sistemas muy mínimos, o las reducciones originales de 21 NP de Karp, pero si tuviera que elegir una, iría con el Teorema de incompletitud de Godel.

“¡Eso no es una prueba informática!” Puedes protestar. Y te equivocas. Es la prueba más científica de la informática. ¡Hacer que los números hablen de sí mismos! Esta es la esencia misma de la informática.

Answer 3

Nomino la prueba que muestra que el problema de detención para las computadoras es recursivamente irresoluble. Además, la prueba de que mostrar dos algoritmos son equivalentes es recursivamente insoluble. El ganador de todos los tiempos, si alguna vez se encuentra, es la resolución del

P = problema NP o que muestra que P = NP es indecidible.