Una prueba de P = NP puede no proporcionar ninguna pista sobre cómo construir o encontrar los algoritmos para realmente colapsar NP en P no tendrá ningún impacto práctico. De hecho, para mí solo hay 2 posibilidades más probables para la pregunta P =? NP. O no es cierto, o es cierto, pero en la práctica no hay forma de encontrar los accesos directos pronosticados en el caso de P = NP. Esta es la razón por la que algunos de nosotros también pensamos que la pregunta está mal planteada porque la suposición subyacente es que P =? NP es muy relevante en la práctica, pero en realidad es muy probable que sea bastante irrelevante.
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 compatibles (o se sospecha que lo es 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 te permite elegir un elemento de un número infinito de conjuntos, algo, en la práctica, imposible) llamado ZFC.
- ¿Cuáles son las puertas lógicas más comunes en las computadoras?
- ¿Cuál es su opinión sobre negarse a dejar que Yann LeCun dé una conferencia en Arabia Saudita en la Universidad de Ciencia y Tecnología King Abdullah debido a la religión?
- ¿Cuáles son algunos de los asombrosos usos de los gráficos en CS / Modelado?
- ¿Cómo pueden contribuir los ingenieros informáticos o los informáticos en el campo agrícola en la India?
- ¿Qué debería preferir: CSE en IIT-G o IIT-BHU o IIT-H?
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, digamos algunas formas de cálculo (análisis matemático), por ejemplo, requieren 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.
