¿El cerebro está resolviendo problemas NP-difíciles?

Answer 1

No hay ninguna razón para creer que el cerebro no esté sujeto a las mismas restricciones que enfrentan otros dispositivos informáticos, por lo que todos sospechan que los casos difíciles de problemas NP-Hard también serán difíciles para el cerebro humano.

En particular, si P! = NP, entonces los problemas de NP-difíciles (como el problema de Travelling Salesman) serán difíciles de resolver (exactamente) a medida que aumenta el tamaño de la entrada. Y, de hecho, aquí no hay ninguna evidencia en particular: las personas son generalmente muy terribles para encontrar soluciones exactas para problemas que son tan complicados.

Hay un par de outs: la gente podría llegar a ser bastante buena resolviendo aproximaciones a problemas difíciles de NP; y / o la gente podría llegar a ser buena resolviendo problemas difíciles de NP exactamente cuando el tamaño de los problemas es muy pequeño …

Pero creo que la mejor respuesta a la pregunta original es: sí, el cerebro se enfrenta a muchos problemas de NP-difícil, pero (hasta donde sabemos) carece de atajos mágicos que faciliten la resolución de tales problemas. exactamente.

Answer 2

Sí, quiero decir, ¿cómo crees que los matemáticos y los científicos de computación elaboran algoritmos para problemas de NP? También vale la pena señalar que los cerebros humanos son capaces de abordar e idear pruebas para cosas que no creemos que las computadoras podrían hacer, como problemas indecidibles (muchos de los cuales se superponen con fuerza NP como el problema de detención).

Vale la pena señalar que no hay razón para sugerir que los humanos tengan una Máquina de Turing en la cabeza, es una buena analogía, pero no hay modelos que demuestren que nuestros cerebros son equivalentes a las Máquinas de Turing. Quiero decir, muchos de los modelos que tenemos para cosas como esta son casos mucho más especiales que tienen una relación 1-1 con Turing Machines, pero muestran fallas en el modelo (p. Ej., Vea la computación de ADN y los modelos de allí). Habría muchas implicaciones filosóficas si tuviéramos cosas análogas a las Máquinas de Turing en nuestra cabeza. Por lo tanto, es vital ver que la dureza NP es un poco tonta de considerar en algún tipo de clasificación con nuestros cerebros como si nuestros cerebros fueran máquinas de Turing como cuando los clasificamos, tenemos que considerar el modelo de cálculo . Sin embargo, creo que el cerebro es definitivamente capaz de resolver problemas NP-difíciles, pero no los llamaríamos NP-hard debido al modelo del cerebro (es una extensión de la aplicación de nuestras matemáticas y su resolución). Estas cosas tienen más sentido considerarlas en las ANN o en otros modelos de este tipo, ya que son formulaciones matemáticas y pueden usarse para resolver problemas. Simplemente no sabemos lo suficiente sobre el cerebro, pero nuestra teoría poco sugiere que los cerebros y las AN son la misma cosa. Hay más cosas en marcha, y los neurocientíficos computacionales tienen mucho trabajo por delante.

Answer 3

Es difícil decir si estamos resolviendo el problema de la misma manera que las computadoras resuelven los problemas de NP fuerte, todavía no hemos descubierto la mecánica de las unidades de procesamiento de nuestros cerebros. Pero lo que sí se sabe es que el cerebro humano se enfrenta a muchos problemas de NP-difícil. Afortunadamente, también tenemos MUCHO más contexto sobre el problema que un programa informático típico sobre el problema. Por contexto, me refiero a una amplia gama. Bajo el popular problema del “vendedor ambulante”, algunos ejemplos son:

• ¿Qué tan importante es la respuesta real (debo resolverla? Puedo llamar enferma la próxima semana)
• ¿Qué tan importante es la precisión (quiero pasar otra hora refinando la respuesta en 5 segundos? ¿Depende mi bono?)
• datos no directos (mi colega John en Londres me debe mucho. Puede hacer las ventas)
• Replanteamiento de lo óptimo (tuve que elegir el regalo de mi tía la semana pasada, tomaré ese desvío de 10 minutos para terminar eso también)
• así sucesivamente …

Ese contexto nos permite hacer soluciones aproximadas aproximadas rápidamente, dejando caer dramáticamente el espacio de la solución. La palabra clave es “aproximada, aproximada”. Entonces, aunque no seamos muy buenos para elegir la “mejor” solución cada vez, somos muy buenos para encontrar una “buena” solución que funcione en muchos casos. En términos de escalar el espacio del problema, estamos bien en el procesamiento de aproximadamente 10-14 variables independientes en nuestra cabeza, mentalmente. Más allá de eso, tenemos que recurrir a la agregación (“todas las ubicaciones del oeste en un solo contenedor”), bocetos y expresiones tabulares como ayuda, por lo que aún permanecemos por debajo de las 10-14 variables mentales independientes.

Entonces, ¿el cerebro está resolviendo problemas NP-difíciles? Sí.
¿Lo está resolviendo necesariamente usando los mismos algoritmos que los solucionadores tradicionales de NP-hard? No.
¿Podemos aprender de esto para la próxima generación de solucionadores? Sí, y actualmente es un área de investigación importante (por ejemplo, aprendizaje automático). Sin embargo, también se requiere un gráfico de conocimiento altamente en red (de temas aparentemente no relacionados) para el contexto asociado que nos permite todos esos atajos prácticos. Es por esto que creo que eventualmente (más de 20 años) los solucionadores de propósitos generales serán más fuertes porque tienen mucho Contextos más fuertes / “conocimiento” / “experiencia” a los que recurrir durante la resolución.

Answer 4

No.

El cerebro puede hacer algunas cosas sorprendentes porque es masivamente paralelo y porque es un sistema de aprendizaje muy versátil con acceso a gran cantidad de datos.

Pero no hay evidencia de que los problemas graves de NP no sean difíciles para los humanos. Por el contrario, pídale a un ser humano que resuelva grandes instancias del problema de la mochila o 3SAT y tenderán a hacerlo peor que un dispositivo informático bien programado.

Algunas personas creen que la inteligencia general requiere algún “ingrediente extra”, que también distinguiría a las personas de las máquinas. Bueno, tal vez, pero no hay evidencia de tal ingrediente, y de hecho podemos observar fácilmente que las cosas que sabemos son necesariamente difíciles para una computadora, y que también son difíciles para los humanos.

Si hay un ingrediente secreto para nuestra conciencia, la capacidad de resolver problemas difíciles de NP no lo es.