¿Por qué las personas son intuitivamente buenas para resolver problemas difíciles de NP?

Answer 1

tl; dr Los humanos son “buenos” para resolver pequeños problemas. Para todo lo demás, no somos mejores que las computadoras.

En realidad, diría lo contrario: que los humanos no son mejores (y en la práctica, mucho peores) que las computadoras para resolver problemas de NP-Hard. Al final del día, todos nuestros métodos humanos de resolución de problemas son solo un conjunto de heurísticas junto con ejemplos anteriores. No se ha demostrado que ningún algoritmo resuelva los problemas de NP-Hard de manera eficiente, y dudo mucho que la mente humana tenga acceso a tal algoritmo.

Puede parecer que somos “buenos” para resolver problemas de NP-Hard de manera eficiente, pero creo que eso se debe a que se trata de pequeños problemas: los que tienen imágenes, fórmulas o entradas que se pueden imprimir literalmente en una pequeña parte. de una sola página. Lo más probable es que esté aplicando heurísticas a cada uno de estos problemas y seleccionando a mano algunas entradas para las que esas heurísticas funcionan bien.

Por ejemplo, considere un problema de vendedor ambulante en un gráfico con 5 vértices y 8 aristas donde, después de una propagación de restricciones triviales en su cabeza, se da cuenta de que solo hay dos ciclos, uno de los cuales es claramente más corto que el otro. O quizás otra heurística que usas es enrutar tantos caminos como sea posible a través del vértice de mayor grado para “dejar tantas opciones como sea posible”. Sin embargo, en realidad no importa, porque estas heurísticas no funcionan en todos los casos. En ese sentido global, no nos dan soluciones mejores / más rápidas (y en la mayoría de los casos, no nos dan ninguna solución).

Te desafío a considerar el mismo problema, pero con un gráfico que tiene vértices de 1M y bordes 1B. Me resulta difícil creer que un humano pueda tener alguna idea de qué bordes forman parte del camino óptimo (en este caso, “dónde comenzar el camino” no importa porque es un ciclo).

Extendería esta línea de razonamiento a todos los problemas algorítmicos en realidad. Tome clasificación, por ejemplo, que está en P y tiene una solución óptima simple. Considere aplicar quicksort a una lista de 5 números. La lista es tan pequeña que probablemente pueda identificar el mejor elemento pivote “muy rápidamente, solo con mirar” (aunque si tuviera que contar con precisión cada paso que estaba realizando en su cabeza, definitivamente sería [math] \ Omega (n )[/mates]). ¿Qué tal si ordenas una lista de mil millones de números? ¿Crees que puedes encontrar un pivote de mediana más rápido que el algoritmo de selección de mediana de tiempo lineal? Si puede, entonces debería poder escribir el algoritmo paso a paso, probar su corrección y mostrar que su tiempo de ejecución es asintóticamente más rápido (por un factor constante en este caso) que la selección de la mediana estándar. Pero si lo ha hecho, entonces acaba de crear otro algoritmo para que lo use una computadora.

Para una discusión un tanto relacionada sobre si la naturaleza puede o no resolver los problemas de NP-Complete “rápidamente”, consulte el documento de Scott Aaronson donde refuta esta afirmación, específicamente sobre las burbujas de jabón que “solucionan rápidamente” el problema del árbol Steiner: http: // www. scottaaronson.com/pap…