Se ha observado que los humanos son buenos para resolver el problema de los vendedores ambulantes bajo ciertas limitaciones. ¿Hay otros problemas NP-difíciles o NP-completos que los seres humanos son buenos para resolver? ¿Ha habido otra investigación (psicológica, neurobiológica) sobre esto?
Una pista que estoy investigando actualmente es cómo los humanos son buenos para jugar Buscaminas, a pesar de que es NP-Complete .
Con respecto a la relación entre el cerebro y la teoría de la complejidad, creo que es importante recordar que el cerebro casi nunca encuentra soluciones exactas a los problemas y parece preferir el razonamiento inductivo a la deducción. ( Cómo inducir computacionalmente una estrategia de buscaminas ) Además, en su mayoría evocamos aproximaciones. Précis of Bayesian Rationality: The Probabilistic Approach to Human Reasoning analiza la resolución de problemas en términos inexactos (probabilísticos). Creo que uno de los artículos de seguimiento (Identificar la respuesta óptima no es un paso necesario para explicar la función, página 85) es relevante para su pregunta:
"Una explicación que requiera una función de respuesta óptima también debe considerar que: (e) para problemas de inferencia inductiva, la respuesta óptima a menudo es analíticamente difícil de determinar con métodos exactos, y no será única; (f) las respuestas conductuales son típicamente aproximadamente óptimas , revelando una tendencia más que una correspondencia"
Las respuestas colectivas se pueden agregar para combinar fragmentos de soluciones comunes en una solución global. Quizás una clave para resolver NP-hard/complete es tener suficiente diversidad, por lo tanto, trabajar en un sentido colectivo. Echa un vistazo a La sabiduría de la multitud en problemas combinatorios, de Sheng Kung Michael Yi,a Mark Steyversa, Michael D. Leea,a Matthew J. Dryb
usuario6682
usuario3503