Este es un concepto interesante. Lance Fortnow tiene un libro (The Golden Ticket) que discute las posibilidades en el mundo después de que se resuelva el problema P vs NP. Pero es interesante reflexionar sobre los pasos en el camino.
Entonces, digamos que se te ocurre un algoritmo para resolver un problema de NP completo. Como no puede probar su tiempo polinomial, realmente no conoce su tiempo polinomial. Para sus propósitos, le importa que se ejecute rápidamente en entradas grandes. De hecho, solo se le ocurrió el problema porque se le pidió que resolviera un problema de NP completo en el trabajo y en lugar de dar la respuesta estándar de “ese es un problema que algunas de las mentes más brillantes del mundo no han podido encontrar un algoritmo que siempre encuentra la solución óptima rápidamente “, en cambio dijiste que echarías un vistazo y lo probarías. Entonces, después de unas semanas, regresa y, de hecho, tiene una solución que funciona para el problema que le dieron.
Pasan unas pocas semanas más y su nombre se está difundiendo en la empresa porque su algoritmo está funcionando bien. De hecho, ha descubierto que no solo resuelve el problema que se le dio, sino que también funciona bien en otros problemas en los departamentos adyacentes. En última instancia, algunas personas acuden a ti diciendo que deberías comenzar a hacer presentaciones sobre tu algoritmo. Estas presentaciones se dirigen a un doctorado en su empresa que le ofrece ayuda para escribir un documento publicando el algoritmo.
- ¿Dónde puedo conectarme en línea para estudiar estructuras de datos, como árboles de búsqueda binarios, montones, etc.?
- ¿Qué es particionar en chispa, por qué lo necesitamos?
- ¿Qué significa front = rear = null y front = rear = -1 en la cola de las estructuras de datos en C ++?
- ¿Cuál es el peor caso de complejidad temporal de BFS (cuando se busca un elemento), sin almacenar los estados visitados?
- Quiero comenzar un proyecto de programación. ¿Cuáles son algunas sugerencias al respecto?
Usted hace esto y, en este primer documento, ofrece el algoritmo como una nueva forma de resolver el problema NP completo. Discuta la investigación que hizo para encontrar el algoritmo, en qué otros algoritmos se basa, algunas métricas de rendimiento y cómo se aplica a problemas de la vida real.
Una vez que se publica, comienza a recibir mucha atención de los algoritmos y la comunidad teórica de la informática. Los investigadores se ponen en contacto con usted y le dicen que van a citar su trabajo como una posible solución a otros problemas completos de NP. Otros citan su trabajo y dicen que las cosas pueden mejorarse cambiando algunas cosas, utilizando diferentes estructuras de datos, comprendiendo las limitaciones, etc.
Entonces, un día, alguien te llama y dice que lo has hecho. Bueno, realmente lo han hecho, pero se basa en tu trabajo. En este caso, el “it” está demostrando que existe un algoritmo de tiempo polinómico para un problema NP-Completo, es decir, que han demostrado que P = NP. Esto cambiará el mundo para siempre porque una de las preguntas más importantes en informática ha sido respondida. Esta prueba será criticada por lo mejor de lo mejor de lo mejor, pero el hecho de que haya habido un zumbido a su alrededor durante un tiempo sofocará algunas sospechas. Sin embargo, el hecho de que muchos creen que P no es igual a NP significa que la prueba será inspeccionada en gran medida (como debería ser cualquier prueba), pero si el algoritmo y la prueba realmente sostienen su nombre (así como el nombre de la persona que finalmente lo pruebe) será legendario.
En resumen, aunque creo que la prueba de dicho algoritmo es lo último que estaríamos buscando, creo que habría pasos notables en el camino que podrías lograr antes de llegar a una prueba. De hecho, muchos (si no todos) de estos pasos tienen lugar con el desarrollo general de un algoritmo o un concepto algorítmico. No recuerdo cómo fue cuando a Fred Glover se le ocurrió Tabu Search, pero me imagino que tuvo un zumbido similar, con la obvia excepción de la prueba definitiva de resolver un problema NP Complete en tiempo polinómico.
