¿Cuál es la clase de complejidad más estrechamente asociada con lo que la mente humana puede lograr rápidamente?

Esta pregunta es algo que me he preguntado por un tiempo.

Cuando las personas describen el problema P vs. NP, a menudo comparan la clase NP con la creatividad. Señalan que componer una sinfonía de calidad de Mozart (análoga a una tarea de NP) parece mucho más difícil que verificar que una sinfonía ya compuesta es de calidad de Mozart (que es análoga a una tarea P).

¿Pero es NP realmente la "clase de creatividad"? ¿No hay muchos otros candidatos? Hay un viejo dicho: "Un poema nunca termina, solo se abandona". No soy poeta, pero para mí, esto es una reminiscencia de la idea de algo para lo que no hay una respuesta correcta definitiva que pueda verificarse rápidamente ... me recuerda más a la coNP y a problemas como la TAUTOLOGÍA que NP o SAT. Supongo que a lo que me refiero es que es fácil verificar cuándo un poema está "equivocado" y necesita ser mejorado, pero difícil de verificar cuando un poema está "correcto" o "terminado".

De hecho, NP me recuerda más a la lógica y al pensamiento de cerebro izquierdo que a la creatividad. Las pruebas, los problemas de ingeniería, los rompecabezas de Sudoku y otros "problemas de cerebro izquierdo" estereotipados son más NP y fáciles de verificar desde un punto de vista de calidad que la poesía o la música.

Entonces, mi pregunta es: ¿qué clase de complejidad captura con mayor precisión la totalidad de lo que los seres humanos pueden lograr con sus mentes? Siempre me he preguntado ociosamente (y sin ninguna evidencia científica que respalde mi especulación) si tal vez el cerebro izquierdo no es un solucionador de SAT aproximado, y el cerebro derecho no es un solucionador de TAUTOLOGÍA aproximado. Quizás la mente está preparada para resolver problemas de PH ... o quizás incluso puede resolver problemas de PSPACE.

He ofrecido mis pensamientos arriba; Tengo curiosidad por saber si alguien puede ofrecer una mejor comprensión de esto. Para plantear mi pregunta de manera sucinta: estoy preguntando qué clase de complejidad debería asociarse con lo que la mente humana puede lograr, y si hay evidencia o un argumento que respalde su punto de vista. O, si mi pregunta está mal planteada y no tiene sentido comparar humanos y clases de complejidad, ¿por qué es este el caso?

Gracias.

Actualización : he dejado todo menos el título intacto arriba, pero esta es la pregunta que realmente quería hacer: ¿Qué clase de complejidad está asociada con lo que la mente humana puede lograr rápidamente ? ¿Qué es el "tiempo humano polinomial", si quieres? Obviamente, un humano puede simular una máquina de Turing con tiempo y recursos infinitos.

Sospecho que la respuesta es PH o PSPACE, pero realmente no puedo articular un argumento inteligente y coherente de por qué este es el caso.

Tenga en cuenta también: estoy principalmente interesado en lo que los humanos pueden aproximar o "hacer la mayor parte del tiempo". Obviamente, ningún humano puede resolver instancias difíciles de SAT. Si la mente es un solucionador de X aproximado , y X está completo para la clase C , eso es importante.

No afirmo que esta sea una respuesta completa, pero aquí hay algunos pensamientos que esperamos estén en la línea de lo que está buscando.

NP corresponde aproximadamente a "rompecabezas" (es decir, la integridad de NP de Sudoku, Buscaminas, Celda libre, etc., cuando estos rompecabezas se generalizan adecuadamente para permitir ). PSPACE corresponde a "juegos de 2 jugadores" (es decir, la integridad de PSPACE del ajedrez, go, etc.). Esto no es noticia.$n \to \infty$

En general, las personas parecen estar bien con instancias finitas de rompecabezas completos de NP, y sin embargo los encuentran no lo suficientemente triviales como para ser entretenidos. Las instancias finitas de juegos completos de PSPACE que jugamos se consideran algunas de las tareas intelectuales más difíciles de este tipo. Esto al menos sugiere que PSPACE está "alcanzando los límites superiores" de nuestras habilidades. (Sin embargo, nuestros oponentes en estos juegos completos de PSPACE generalmente son otras personas. Incluso cuando los oponentes son computadoras, las computadoras no son oponentes perfectos. Esto se dirige hacia la cuestión del poder de las pruebas interactivas cuando los jugadores son computacionalmente limitados. también el tecnicismo de que algunas generalizaciones de estos juegos son EXP-complete en lugar de PSPACE-complete.)

Hasta cierto punto, los tamaños de los problemas que surgen en los rompecabezas / juegos reales se han calibrado según nuestras capacidades. Sudoku 4x4 sería demasiado fácil, por lo tanto, aburrido. 16x16 Sudoku tomaría demasiado tiempo (no más que la vida del universo, pero más de lo que la gente está dispuesta a sentarse para resolver un rompecabezas de Sudoku). 9x9 parece ser el tamaño de "Ricitos de oro" para las personas que resuelven Sudoku. Del mismo modo, jugar Free Cell con un mazo de 4 palos de 13 cartas cada uno y 4 celdas gratis parece ser la dificultad correcta para ser solucionable pero desafiante para la mayoría de las personas. (Por otro lado, una de las personas más inteligentes que conozco es capaz de resolver juegos de Free Cell como si solo estuviera contando números naturales "1,2,3,4, ...") De manera similar para el tamaño de Go and Chess tableros.

¿Alguna vez has intentado calcular un permanente 6x6 a mano?

Supongo que el punto es que si tomas problemas naturales en las clases significativamente por encima de PSPACE (o EXP), entonces las únicas instancias finitas que las personas son capaces de resolver parecen ser tan pequeñas que no son interesantes. Parte de la razón por la cual "natural" es necesario aquí es que uno puede tomar un problema natural, luego "antinaturalmente" modificar todas las instancias de tamaño para que para todas las instancias un humano intente que el problema se vuelva totalmente intractible, independientemente de su complejidad asintótica.$< 10^{10}$

Por el contrario, para problemas en EXP, cualquier tamaño de problema por debajo del "talón de lo exponencial" tiene la posibilidad de ser solucionado por la mayoría de las personas en cantidades razonables de tiempo.

En cuanto al resto de PH, no hay muchos (¿ninguno?) Juegos naturales que las personas jueguen con un número fijo de rondas. Esto también está relacionado de alguna manera con el hecho de que no conocemos muchos problemas naturales completos para niveles de PH superiores al tercero.

Como mencionó Serge, FPT tiene un papel que desempeñar aquí, pero (creo) principalmente en el hecho de que algunos problemas tienen naturalmente más de un "tamaño de entrada" asociado con ellos.

La tesis de Cognition Tractable postula que las capacidades cognitivas humanas están limitadas por la capacidad de cálculo computacional. De esta manera, la tesis P-Cognition utiliza el tiempo polinomial determinista como modelo para la trazabilidad computacional, mientras que en el siguiente documento, se argumenta que la tesis FPT-Cognition es más apropiada. Vea el artículo de Iris van Rooij en la edición de junio de 2009 del Boletín de Complejidad Parametrizada para una discusión más detallada y sugerencias para otros documentos.

• Iris van Rooij. La tesis de la cognición manejable . Cognitive Science, 32, pp. 939-984, 2008.
• Iris van Rooij. Parámetros que hacen que el trabajo cognitivo sea ligero. Noticias FPT: Boletín de Complejidad Parametrizada, junio de 2009 .

Creo que uno es llevado al modelo equivocado al tratar de extrapolar a partir del tipo de cosas que el cerebro humano parece calcular, y creo que sería mejor tener una visión opuesta y, en su lugar, extrapolar del modelo computacional que es.

$TC^0$

Además, no estoy de acuerdo con la afirmación de la pregunta de que la mente humana puede simular una máquina de Turing. Más bien, lo que puede hacer es simular el control finito de la máquina Turing. Para realizar tareas muy complicadas, parece necesario poder grabar información en una "cinta".

Las clases de complejidad se definen en términos de complejidad asintótica, por lo tanto, no se asignan bien a las capacidades cognitivas de los humanos, que necesariamente se limitan a los tamaños de problemas limitados.

La regla general es: si algo es fácil para una computadora, entonces puede ser difícil para un humano, y viceversa, si es difícil para una computadora, puede ser fácil para un humano.

Aquí "fácil / difícil para una computadora" se refiere a la capacidad de rastreo práctica, no a una clase de complejidad abstracta.

Por ejemplo, agregar una lista de mil millones de enteros es fácil para una computadora moderna y difícil para un humano, mientras que producir una descripción verbal de una imagen es fácil para un humano pero difícil (actualmente imposible en el caso general) para una computadora.

La investigación de Inteligencia Artificial demostró que muchas tareas cognitivas que los humanos y los animales realizan fácilmente, en algunos casos, incluso inconscientemente, pueden modelarse como problemas NP-difíciles. Los humanos no pueden encontrar soluciones óptimas a estos problemas para todos los tamaños, pero sí pueden encontrar soluciones heurísticas para tamaños prácticos mucho mejor que los algoritmos de IA más conocidos.

También tenga en cuenta que la distinción entre el cerebro izquierdo y el cerebro derecho que menciona es demasiado simplista y obsoleta. La lateralización de las funciones cerebrales es mucho más sutil e incluso puede variar de un individuo a otro.

Si elegimos estudiar el cerebro humano en sí mismo en lugar de cómo los humanos usan su cerebro para resolver problemas, no creo que sea un problema de complejidad, sino de computabilidad. Dado que cada TM necesita una función de transición, un humano puede imitar los pasos de la TM, por lo tanto, el cerebro humano está Turing completo.

En la dirección inversa, ¿pueden los TM calcular todo lo que hacen los humanos? La respuesta corta es que no lo sabemos. Asumiendo que la tesis de la Iglesia-Turing es cierta, si la respuesta cambiará o no depende de su visión del mundo (filosófica, espiritual, religiosa y de otro tipo). En ese caso, podemos decir con seguridad que el cerebro humano como parte del mundo material puede ser simulado por una máquina de Turing. El resto está a debate y, al menos en mi opinión, no está relacionado con TCS.

$P \neq NP$$NP-P$$10^{10^{100}}n$$n$$2 \log 10^{10^{100}}$veces más información en cada paso del algoritmo acelerado. Por supuesto, se necesitaría un límite inferior específico para garantizar que no exista un algoritmo más rápido (constantes incluidas).

Entonces, si desea calcular con precisión qué problemas tiene el cerebro humano, dadas las limitaciones de la vida real, como distracciones, capacidad de atención, etc., debe tener un límite superior en el número de pasos realizados en total, un límite superior en el número de pasos seguidos (incluso el investigador más devoto debe dormir y comer), una limitación en el espacio (no solo en la cinta, sino también en cualquier registro "interno"), una simulación de cómo actúa la memoria porque a diferencia de las TM, nosotros podemos olvidar algo que escribimos en nuestra "cinta de trabajo" o el estado exacto y, por supuesto, determinar la relación entre los pasos de tiempo de la máquina y el tiempo en segundos o "pasos del cerebro humano". Quizás surjan otros problemas a medida que avanza. En un giro irónico, quizás uno o más de este problema no puede ser resuelto por el cerebro humano, al menos de manera eficiente.

${\bf ThC}_0$$\bf{P}$$\bf NC$$\bf \#P$

Si le das a un humano un lápiz y papel, puede resolver casi cualquier problema, actuando como una máquina. Así que creo que este no puede ser el punto.

En mi opinión, lo que hace que el pensamiento humano sea la abstracción, es decir, los humanos no manejan las cosas (en primer lugar), crean puntos de vista sobre las cosas. Aunque, como debo admitir, no puedo proporcionar ninguna teoría para abstracción casi lista para usar.

| =

He estado pensando en esta pregunta durante mucho tiempo. Esto es a lo que he llegado: los

humanos pensamos generalmente en objetos mentales abstractos y no en algoritmos. Los números que conocemos, el idioma que hablamos, el pensamiento alguna vez fue una idea abstracta. Estas ideas fueron extendidas por filósofos, científicos y luego puestas en práctica. Lo que tenemos es diferente de cómo se originaron.

Su pregunta: "¿Qué clase de complejidad captura con mayor precisión la totalidad de lo que los seres humanos pueden lograr con sus mentes?" solo se puede responder si hay pruebas suficientes de que los humanos siguen modelos matemáticos / algorítmicos / probabilísticos. Bueno, podrían seguir cada uno de los anteriores o una combinación de ellos. Pero en realidad son algo diferente. Esto es solo un pensamiento humano normal. Desglosar los pensamientos creativos como la composición de Mozart, un poema o el pensamiento de un deportista en formas formales respectivas (métodos matemáticos / lógicos de su pensamiento) y tratar de generalizar sería una hazaña, aunque no estoy seguro de si eso será posible.

También creo que podríamos aproximarnos a la clase de complejidad, pero nunca podemos estar seguros.