Probablemente nunca como se dice hoy. Para mí, solo hay 2 posibilidades más probables para la pregunta P =? NP. O P =! NP, o P = NP está probado, pero en la práctica no hay forma de encontrar los algoritmos para hacer que cada problema en NP sea un problema en P. Esto es realmente por qué algunos de nosotros pensamos que la pregunta puede estar mal planteada porque la suposición subyacente es que P =? NP es muy relevante en la práctica (por ejemplo, descifrar algoritmos basados en funciones unidireccionales como el cifrado RSA), pero en realidad es muy probable que sea irrelevante en la práctica.
Por ejemplo, una prueba teórica no constructiva puede colapsar todas las clases de complejidad, pero en la práctica pueden sostenerse porque el algoritmo en P es demasiado difícil en la práctica (como en teoría también debería estar en P si P = NP) para encontrar, si no es imposible, o en última instancia, existen restricciones físicas (por ejemplo, un argumento termodinámico) a lo que realmente puede hacer, especialmente si una prueba no constructiva no proporciona los medios para producir el algoritmo en P para uno previamente conocido en NP. Por el contrario, si es poco probable como lo creo, no solo P = NP, sino que encontramos una manera de encontrar el algoritmo en P para cualquier problema que se crea en NP, entonces el impacto será enorme para todas las áreas de la ciencia y la tecnología.
En realidad, es bastante simple ver cómo una prueba para P = NP puede no implicar nada. Esto es cambiando el marco estándar de cálculo. Ha habido, por ejemplo, sugerencias que tiene P = NP. Sin embargo, las pruebas que muestran esto hacen uso de formas de cómputo no estándar que están etiquetadas con el nombre místico de ‘hipercomputación’, es decir, el uso de cierto tipo de computadoras con capacidades extraordinarias, como ser arrojado a un agujero negro y a la computadora aún funciona y le devuelve los resultados de un cálculo, o una computadora que puede calcular más rápido de lo que permite la termodinámica, y así sucesivamente. Puede pensar entonces que tales modelos ‘divertidos’ obviamente deberían estar prohibidos, sin embargo, si se acerca a P = NP desde el punto de vista puramente matemático, los matemáticos cambian sus marcos todo el tiempo (especialmente cuando buscan probar teoremas a toda costa , por ejemplo, forzar), incluso haciendo uso común de sistemas axiomáticos no constructivos / no computables (o muy sospechosos si no tiene una computadora con propiedades extraordinarias como las que acabo de describir), como Set Theory con El Axioma de Elección (un axioma que le permite elegir un elemento de un número infinito de conjuntos, algo, en la práctica, imposible) llamado ZFC.
- Informática teórica: ¿son todos los lenguajes P decidibles? ¿Son todos los idiomas NP decidibles?
- ¿Qué notación asintótica se usa con más frecuencia para los algoritmos y por qué?
- ¿Por qué diferenciamos entre máquinas Turing universales y máquinas Turing normales?
- ¿Cuál es el significado de los idiomas [math] \ omega [/ math] en informática?
- ¿Cuántas matemáticas se necesitan en la codificación?
Por lo tanto, las teorías matemáticas que requieren este tipo de poder ‘infinito’ también son no construibles / no computables y son muy comunes hasta el punto de que los matemáticos rara vez preguntan el marco en el que se ha demostrado un teorema cuando quieren reutilizarlo para algo más. Tampoco siempre está claro qué otros sistemas de axiomas matemáticos, por ejemplo, algunas formas de cálculo (análisis matemático), necesitan toda la potencia de ZFC (la mayoría de las teorías matemáticas lo hacen), por lo que en la práctica, incluso algunos teoremas que se consideran ‘ se demostró que ‘puede estar usando este tipo de’ truco ‘que en teorías construibles / computables, como las sugeridas para P = NP, uno diría inmediatamente que no deberían permitirse. Sin embargo, al final, incluso ese tipo de matemática resulta ser extremadamente útil, incluso en tareas muy constructivas como la práctica de la ingeniería y la tecnología, incluso si las teorías en sí mismas no son construibles.
Entonces, ahora puede ver el problema, si la pregunta de P = NP no siempre viene con el marco esperado en el que desea que sea cierto o no, o las condiciones para las que desea que se demuestre o refute. Y es el caso de que el marco implícito de la pregunta es el modelo de cálculo de Turing, pero parece que el marco está incompleto si no incluye el tipo de condiciones más precisas que cuantifican si la respuesta realmente puede producir los algoritmos en P para todos los problemas previos en NP, o si se puede permitir una prueba puramente no constructiva, por ejemplo, utilizando sistemas de axiomas generales, empujando la pregunta P =? NP a la irrelevancia en la práctica, ya que estaría desconectada del sentido mismo (de factibilidad) en que se hizo la pregunta.
