Los problemas en la clase NP son fáciles de resolver: simplemente pruebe todas las ramas de cómputo posibles, recopile resultados y luego compare. Esta es una solución de fuerza bruta para cada problema y funcionará. Sin embargo, el problema en los problemas de NP es que esta es la única solución que conocemos para ellos. Sabemos cómo resolverlos, pero no podemos aplicar la solución en realidad porque nunca hay suficientes recursos computacionales para descifrar estas bestias. Hay demasiadas ramas posibles que tendríamos que buscar y comparar, y en una máquina de Turing determinista nos vemos obligados a buscarlas de una en una. En teoría, donde podemos inventar una máquina de Turing no determinista que puede buscar todas las ramas a la vez y luego los problemas de NP son fáciles; acabo de escribir un algoritmo de fuerza bruta y ejecutarlo con una máquina de Turing no determinista. Pero esta máquina de Turing no determinista no puede existir en realidad porque tiene algunas propiedades desagradables. Para que ese tipo de máquina funcione, debería ver el futuro. Debe saber de antemano qué ramas vale la pena buscar. Luego, puede seleccionar las mejores ramas y recopilar los resultados. La mayoría de las heurísticas para problemas de NP utilizan esta idea previsible cuando intentan estimar qué ramas valen la pena buscar. Sin embargo, cada heurística tiene sus límites: generalmente no producen soluciones óptimas y funcionan solo para ciertos tipos de entrada.
Entonces, los problemas en NP no son fáciles debido a esta explosión computacional; no importa cuán rápido inventemos las computadoras, estos problemas permanecen en NP. A pesar del trabajo muy intenso, todavía nos preguntamos si P = NP (los problemas en P son fáciles). Siempre me ha intrigado por qué es eso, por qué hay una clase de problemas que solo demuestran su intratable capacidad cada vez. Hemos estado tan cerca muchas veces, pero los problemas en NP tienen alguna propiedad especial que los honra a la clase NP. Por ejemplo, encontrar una ruta más corta en un gráfico no es un problema de NP, pero encontrar la ruta más larga sí lo es. Hay una línea delgada entre P y NP, pero esa línea nunca se ha cruzado. En este punto, quiero felicitar a Bartosz Milewski y sus excelentes conferencias en YouTube. En una de sus conferencias sobre teoría de categorías, me dio esta idea perspicaz que cambió por completo la forma en que pienso sobre las matemáticas: creo que la razón subyacente por la cual los problemas en NP son más allá de las computadoras va más allá de las computadoras. nuestro propio pensamiento y cómo los humanos resuelven problemas. Cuando se nos presenta un problema, la única forma de resolverlo es dividirlo en pedazos pequeños y resolver cada pieza individualmente. Luego recogemos las piezas y formulamos una solución para el problema completo. Este estilo de resolución de problemas es visible en todas partes; simplemente no sabemos cómo resolver los problemas de una vez. Nuestra matemática se basa en esta suposición de que los problemas pueden dividirse en pequeñas piezas y luego recuperarse. Pero los problemas en NP no parecen seguir esta estrategia de resolución de problemas. No se pueden dividir en piezas porque cada pieza es parte de una solución completa y no se pueden resolver individualmente. Incluso las soluciones óptimas para piezas individuales no nos darán una solución óptima para el problema completo. Cuando aplicamos nuestro martillo de resolución de problemas a ellos, lo único que podemos hacer es aplicar fuerza bruta.
- Cómo convertirse en un investigador / desarrollador de teléfonos inteligentes
- ¿Es Giga Flops una forma confiable de comparar la velocidad de los procesadores de la computadora (no le interesa la potencia u otros parámetros)?
- ¿Cuál es un escenario de la vida real en el que [matemática] e ^ x [/ matemática] podría usarse?
- ¿Cuál es la diferencia entre Tree y spanning tree?
- Si suponemos que los humanos son una pizarra en blanco (Locke), ¿cuál es la diferencia entre nosotros y la máquina (inteligencia artificial)?
