Es una pregunta muy interesante:
Primero, te dejo leer una situación similar:
El programa de Hilbert es un sistema matemático simple para probar la consistencia de cualquier sistema matemático.
Los teoremas de incompletitud de Gödel se dividen en dos partes:
- Un sistema matemático no puede probar su consistencia.
- Un sistema matemático no puede probar la consistencia de un sistema matemático complejo más alto.
Lejos de la parte matemática \ teórica:
Permítanme decir que la complejidad del problema (encontrar el algoritmo para resolver un problema) es R-difícil (no se conoce una solución, o se desconoce el tiempo de ejecución de la solución). El único algoritmo conocido es:
- Estoy comenzando un proyecto de clasificación de picos, ¿dónde encuentro datos sin procesar y / o simulados?
- ¿Cómo es posible que algún algoritmo sea más rápido que cualquier otro algoritmo similar para algunos valores de la variable de entrada y más lento para otros valores?
- ¿Qué tipo de algoritmo de Machine Learning debería usar para un robot que ve?
- ¿Qué puedes hacer con los algoritmos?
- ¿Cómo lidiar con la gestión eficiente de versiones y la compresión de múltiples versiones para bases de datos científicas?
- dejemos que L sea la representación binaria del problema (por ejemplo, un script de prueba).
- Para i = 0 a infinito:
- Ejecute el programa binario i-ésimo contra L.
- Si el programa terminó y da la respuesta de escritura, interrumpa.
El algoritmo tiene un tiempo de ejecución desconocido. Incluso si excluimos los programas que no se ejecutarán por errores de sintaxis, errores de tiempo de ejecución, etc., podemos encontrar programas maliciosos, programas que se ejecutan para siempre, etc.
Hay una prueba de que el problema puede tener una solución más eficiente en un tiempo de ejecución determinista si P es igual a NP.
Volviendo a la pregunta principal. La respuesta ahora depende de la representación binaria del problema en sí. Entonces la pregunta será “¿podemos probar este algoritmo?”. En general, es posible, pero dado que suponemos que P no es igual a NP (porque no conocemos ningún algoritmo para resolver ningún problema de NP completo), el algoritmo y el script de prueba tardarán para siempre.
