Teoría de la complejidad computacional: ¿cómo es posible que P! = NP no se haya probado todavía?

En el momento en que te sientes y trates de demostrar que no puedes hacer algo matemáticamente con respecto a los algoritmos, comprenderás lo difícil que es este problema. Debe tener una base rigurosa si se quiere demostrarlo, y actualmente creo que carecemos de las matemáticas necesarias para atacar el problema en ese sentido. Incluso si no tenemos una respuesta formal, ha dado lugar a numerosos resultados importantes en Ciencias de la Computación y ha servido para construir gran parte del marco en el que hablamos sobre problemas con bastante frecuencia en nuestro campo. Conocemos muchas formas de probar P = NP, y desafortunadamente, estas no funcionan bien cuando realmente intentas hacerlo (lo que lleva a la gente a pensar P! = NP, entre otras razones). Desafortunadamente, no tenemos demasiadas ideas sobre cómo mostrar P! = NP.

Su ejemplo más básico sería encontrar un algoritmo de tiempo polinómico para un problema de NP completo. Si puedes, P = NP. Bueno, ¿puedes mostrar que no existe un algoritmo que tome tiempo polinómico para resolver el problema NP-completo? Estás hablando de todos los algoritmos posibles que toman tiempo polinomial determinista. Esa no es una tarea fácil de lograr en lo más mínimo.

Bueno, eso suena desafiante, encontremos algo aún más fácil de hacer. Oh, lo sé, podemos ver la dureza de los resultados de aproximación. Muchos de estos resultados utilizan el supuesto de que P! = NP para afirmar la inexistencia de ciertos algoritmos de aproximación. Esto es bastante efectivo en la forma en que las personas en mi área investigan. Si contradice el resultado de la dureza, puede mostrar P = NP. Déjame darte uno de varios ejemplos existentes.

Puede recordar el problema del vendedor ambulante. Créalo o no, si puede encontrar algún algoritmo que en el tiempo polinomial produzca un recorrido TSP con un costo como máximo algunas veces constantes el costo objetivo óptimo de cualquier recorrido TSP para una instancia dada, mostrará P = NP.

Ahora, la pregunta que debo enfatizar, ¿cómo descarta la posibilidad de que algún día alguien pueda diseñar un algoritmo de tiempo polinomial (no estoy afirmando que descartar esto pruebe P! = NP, solo es una pregunta retórica) ? Si bien es poco probable, el método que describí anteriormente podría conducir a una prueba P = NP, solo que no sabemos cómo. Muchas pruebas fallidas de P! = NP afirmarán la dificultad de algún problema, luego simplemente diga “oh, no puede resolver esto de manera eficiente en tiempo polinómico” sin demostrarlo realmente (y generalmente está mal o no lo que realmente piensan que es) veces), ya que solo empuja la carga a otro problema (por lo general, esto entre otros puntos termina siendo la caída de la prueba). Si quieres ver algunos intentos, mira aquí: página P-versus-NP.

Lo sé. Parece tan obvio que algunos problemas en NP como el problema del vendedor ambulante deben requerir
(a) buscar exhaustivamente en todo el conjunto de posibilidades,
(b) que es exponencial en relación con
(c) la cantidad de información requerida para describir el problema.

Pero tan pronto como comience a probar esto, debe enfrentar el hecho de que no comprende completamente por qué esto debe ser necesariamente así, por lo que no puede probarlo. Incluso (c), ¿cuál es la métrica con respecto a la cual se mide la complejidad está sujeta a preguntas como “¿Existe una forma alternativa de describir el mismo problema fundamental que haría que sea más fácil de resolver?” Por ejemplo: las transformadas de Laplace y las transformadas de Fourier hacen que algunos problemas matemáticos sean más fáciles de resolver, y no sabemos si existe algo similar que ayude a decidir el debate P vs NP.

Además, ¿por qué exactamente necesitamos buscar exhaustivamente en todo el espacio de posibilidades para resolver estos problemas? Parece obvio que algunos problemas de NP requerirían esto porque es muy fácil describir una máquina de Turing no determinista que explora un conjunto exponencial de posibilidades en tiempo lineal, pero no lo sabemos con certeza porque entendemos cómo describir la computación problemas y cómo se resuelven no es lo suficientemente completo.

Quiero decir, tenemos cálculos lambda y máquinas de Turing, que fueron un gran avance en nuestra comprensión abstracta de los procesos computacionales en comparación con lo que teníamos antes (intuición no formalizada), pero hasta ahora no han sido suficientes para abordar este particular problema y no sabemos con certeza si es porque no hemos sido lo suficientemente inteligentes en la forma en que usamos nuestras abstracciones existentes, o porque necesitamos abstracciones adicionales relacionadas con la descripción del problema o la representación algorítmica, o algo completamente diferente.

¿Qué es tan obvio acerca de cómo podemos sortear las barreras de algebrización y relativización? El problema P vs. NP parece que debería ser fácil de resolver, pero tan pronto como comience a ver los detalles, queda muy claro que no vamos a obtener una respuesta pronto.

P! = NP puede no ser demostrable. Por ejemplo, se ha demostrado que en la teoría de números, hay afirmaciones que son verdaderas pero que no pueden demostrarse que son verdaderas utilizando el marco de la teoría de números (los axiomas y las reglas). Por lo tanto, es posible que P! = NP sea un problema.
Para probar P! = NP o P = NP, podríamos tener que agregar algunos axiomas / reglas adicionales que no pueden ser probados por el marco existente de la teoría de la complejidad, y que son consistentes con el marco existente.

Entonces podemos intentar probar que P! = NP (0r P = NP) no es demostrable dentro del marco actual.
Pero espera. ¡Puede ser cierto que la demostrabilidad de P! = NP dentro del marco no es demostrable! Y así.
(La última parte de esto es un poco espeluznante. Si es así, ¿llega al infinito? ¿Entonces si el infinito es contable o incontable?)

Un problema interesante en este contexto es el de la Hipótesis Continua, planteada como un problema por Hilbert, que pregunta si hay un conjunto con cardinalidad más que el de los números naturales, pero menos que el de los números reales. Adivina qué: ni esta afirmación ni su negación están implícitas en la teoría de conjuntos, por lo que cualquiera de ellas puede ser elegida y se puede formar una nueva teoría de conjuntos, que estará de acuerdo con los resultados de la Antigua.
PD: No soy un experto en el campo, así que corrígeme si me equivoco. Esta es sólo mi opinión. El etc. fue espeluznante 😀

¿Podría ser, porque el problema es difícil? Bien podría haber preguntado por qué la conjetura de Fermat (erróneamente llamada El último teorema de Fermat) tardó más de 300 años en resolverse. Su declaración es la simplicidad misma. Un niño de diez años podía entender el problema de Fermat, pero los mejores matemáticos del mundo se rompieron la cabeza sobre el problema y la mayoría de los que intentaron resolverlo fallaron.

Otro problema de sonido simple, la Conjetura de Collatz está lejos de resolverse.

Así que no me sorprende que el problema P, NP se resista a la resolución. Ser simple de decir no implica simple de resolver o resolver.