Voy a simplificar en exceso aquí.
Hay una clase de problemas “P” que son difíciles de resolver, pero que se pueden resolver con trucos o con un gran esfuerzo y que a menudo se pueden resolver “suficientemente bien” adivinando inteligentemente. La P significa “polinomio”, ya que existe una relación polinómica (cuadrado, cubo, etc.) entre el tamaño del problema y el trabajo para encontrar una solución. (Duplicar el tamaño hace que sea cuatro veces más trabajo resolverlo, o algo así).
Hay otra clase de problemas “NP” que son difíciles de resolver, y para los cuales no se conocen buenos atajos. La descripción técnica es que verificar si una respuesta a un problema NP es correcta es un problema P. Los problemas de NP suelen ser “exponenciales”, por lo que si agrego 1 al tamaño de un problema, podría ser el doble de difícil de resolver.
- ¿Qué criterios utiliza para determinar si un artículo / publicación es útil para usted?
- ¿Puedo ser un gran programador si no soy bueno en matemáticas? ¿Cómo puedo mejorar mis habilidades matemáticas?
- ¿Qué tipo de matemática debo esperar para ingresar a una especialización en informática?
- ¿Cuál es la diferencia entre la simulación de Monte Carlo y la simulación estocástica?
- Cómo entender las matemáticas del algoritmo de propagación hacia atrás en redes neuronales
Además, algunas personas inteligentes han demostrado que todos los diferentes problemas de NP son más o menos iguales, ya que si uno resulta solucionable, los otros también lo son.
Nadie sabe si todos los problemas “NP” son realmente solo problemas “P” disfrazados. Esta pregunta ha estado abierta desde 1971.
Si P = NP, entonces significa que todos los problemas de NP son en principio solucionables mediante trucos inteligentes. Si P no es NP, entonces los problemas de NP probablemente no se puedan resolver en principio.
Por “solucionable” realmente estoy hablando de formas que son más rápidas que simplemente probar todas las soluciones posibles para ver si una funciona. Siempre puedes hacer eso.
A continuación, gran parte de nuestra seguridad actual de Internet depende de que los problemas de NP sean realmente difíciles de resolver, por lo que si resulta que P = NP, gran parte del software de cifrado y demás de los que todos dependemos ya no serán confiables.
