¿Es probable que algún día los algoritmos de aprendizaje automático evolucionen para resolver problemas completos de NP?

Depende al menos en parte de lo que quiere decir con “resolver”. Un problema NP-completo es un conjunto de cadenas binarias, y resolverlo significa tener un algoritmo de tiempo polinómico que siempre decide correctamente si una cadena dada está en el conjunto. En el aprendizaje automático, a veces permitimos que el algoritmo haga que la función de membresía sea incorrecta siempre que podamos controlar la tasa de error al ingresar más datos. Obtener un clasificador que nunca comete errores requiere datos infinitos, por lo que, en ese sentido, no podemos usar el aprendizaje automático para resolver problemas de NP completo.

Sin embargo, si permite alguna probabilidad de error, entonces es una pregunta abierta. La clase de conceptos aprendibles de PAC de manera eficiente es muy similar a la clase de complejidad BPP, que es la clase de problemas que se pueden resolver en tiempo polinómico con cierta probabilidad de error. Si cada problema de NP completo se puede aprender de manera eficiente PAC, eso implica que [math] \ text {NP} \ subseteq \ text {BPP} [/ math]. No sabemos si ese es el caso, pero creo que la mayoría de la gente en TCS asumiría que no lo es.

También hay cierta dureza de los resultados de aproximación que podrían presentar un problema para obtener soluciones arbitrariamente buenas para problemas de NP completo utilizando el aprendizaje automático. Sin embargo, esa es solo mi intuición, y no creo que pueda hacer una prueba formal de ello.

(La clase de conceptos aprendibles de PAC de manera eficiente está contenida en BPP. Eso es fácil de mostrar. No sé si BPP es de hecho igual a esa clase, y una búsqueda rápida en Google no muestra nada, por lo que sospecho que es un problema abierto)

1- Los problemas completos de NP son aquellos para los cuales no se ha encontrado el algoritmo más eficiente.

2- Los algoritmos de aprendizaje automático son un subconjunto de algoritmos y podría haber muchos algoritmos NP-Complete utilizados entre los algoritmos de aprendizaje automático. Entonces, para implementar algoritmos de aprendizaje automático, necesitamos algunas veces usar algoritmos NP-complete en primer lugar.

3- En nuestra vida cotidiana se utilizan muchos algoritmos NP-complete. El problema del vendedor viajero es uno de ellos que en realidad se resuelve todos los días, incluso por las abejas melíferas.

4- Resolver un problema de NP completo es diferente de encontrar los algoritmos más eficientes para ellos.

5- Si su pregunta es que si las máquinas basadas en algoritmos de aprendizaje automático pueden encontrar los algoritmos más eficientes para tales problemas, entonces hay un gran malentendido en el formalismo de la pregunta:

• Si podemos demostrar que existe un algoritmo más eficiente para los problemas del conjunto de problemas NP-completos, entonces el algoritmo más eficiente ya se ha encontrado para todo el conjunto.
• Entonces, una máquina que puede resolver uno, puede resolver todo.

Si su pregunta es sobre la posibilidad de tal caso, debe comprender que nadie puede responder la pregunta, porque nuestra pregunta en primer lugar no es encontrar el algoritmo más eficiente para problemas NP-completos, sino responder a una pregunta más pregunta básica:

• ¿Hay alguna solución posible? Estos son los llamados problemas P vs NP.

Si alguien aquí pudiera responder esa pregunta sobre usted, no habría perdido el tiempo respondiendo su pregunta aquí, pero habría escrito un artículo para ganar un millón de dólares de elogios por responder esa pregunta.

Los métodos de aprendizaje automático basados ​​en algoritmos no pueden resolver problemas completos de NP en ningún momento. Sin embargo, los métodos basados ​​en ANN (Attractor Neural Network) tienen la esperanza de algún día resolver muchos problemas de NP completo. Por lo tanto, hay una extensa investigación mundial sobre métodos de hardware y software basados ​​en ANN para resolver tales problemas. Robotronics LLC | Facebook

Consulte mi respuesta aquí: ¿Podemos aplicar el aprendizaje automático a los problemas de NP Complete?

Como se mencionó anteriormente, probar P? = NP y usar la heurística para aproximar un espacio de respuesta son dos cosas diferentes.

Russell Impagliazzo tiene una excelente respuesta para la situación donde P <> NP. Solo quiero agregar que si resulta que P = NP = NP completo, entonces el aprendizaje automático podría ser una de las herramientas que podrían conducir a ese descubrimiento y / o prueba.