Qual é a classe de complexidade mais intimamente associada ao que a mente humana pode realizar rapidamente?

59

Esta pergunta é algo que eu me pergunto há um tempo.

Quando as pessoas descrevem o problema P vs. NP, geralmente comparam a classe NP à criatividade. Eles observam que compor uma sinfonia com qualidade Mozart (análoga a uma tarefa NP) parece muito mais difícil do que verificar se uma sinfonia já composta é de qualidade Mozart (análoga a uma tarefa P).

Mas NP é realmente a "classe da criatividade?" Não existem muitos outros candidatos? Há um velho ditado: "Um poema nunca termina, apenas é abandonado". Não sou poeta, mas, para mim, isso lembra a idéia de algo para o qual não existe uma resposta certa e definitiva que possa ser verificada rapidamente ... isso me lembra mais de coNP e problemas como TAUTOLOGY do que NP ou SAT. Acho que estou entendendo que é fácil verificar quando um poema está "errado" e precisa ser aprimorado, mas difícil verificar quando um poema está "correto" ou "terminado".

Na verdade, NP me lembra mais a lógica e o pensamento do cérebro esquerdo do que a criatividade. Provas, problemas de engenharia, quebra-cabeças do Sudoku e outros problemas estereotipados do cérebro esquerdo são mais NP e fáceis de verificar do ponto de vista da qualidade do que a poesia ou a música.

Então, minha pergunta é: qual classe de complexidade captura com mais precisão a totalidade do que os seres humanos podem realizar com suas mentes? Sempre me perguntei à toa (e sem nenhuma evidência científica para apoiar minha especulação) se talvez o cérebro esquerdo não seja um solucionador aproximado de SAT, e o cérebro direito não seja um solucionador aproximado de TAUTOLOGIA. Talvez a mente esteja preparada para resolver problemas de PH ... ou talvez possa até resolver problemas do PSPACE.

Eu ofereci meus pensamentos acima; Estou curioso para saber se alguém pode oferecer idéias melhores sobre isso. Para afirmar minha pergunta de maneira sucinta: estou perguntando qual classe de complexidade deve ser associada ao que a mente humana pode realizar e por evidências ou argumentos que apóiam seu ponto de vista. Ou, se minha pergunta é incorreta e não faz sentido comparar humanos e classes de complexidade, por que esse é o caso?

Obrigado.

Atualização : Eu deixei tudo, exceto o título intacto acima, mas eis a pergunta que eu realmente queria perguntar: Qual classe de complexidade está associada ao que a mente humana pode realizar rapidamente ? O que é "tempo humano polinomial", se você quiser? Obviamente, um humano pode simular uma máquina de Turing, com tempo e recursos infinitos.

Suspeito que a resposta seja PH ou PSPACE, mas não consigo realmente articular um argumento inteligente e coerente sobre por que esse é o caso.

Observe também: estou interessado principalmente no que os humanos podem aproximar ou "fazer na maioria das vezes". Obviamente, nenhum ser humano pode resolver instâncias difíceis do SAT. Se a mente é um resolvedor X aproximado e X é completo para a classe C , isso é importante.

Philip White
fonte
18
+1 por apontar que surpreendentemente muitos desafios de design da vida real têm algum sabor de coNP. Aplica-se também à engenharia. Se uma máquina quebrar ou uma ponte entrar em colapso, é uma prova facilmente verificável de que o projeto estava ruim, mas como provar que um projeto é bom ...?
Jukka Suomela
4
O cérebro é um dispositivo físico e, portanto, finito. A classe de complexidade que você está procurando é um subconjunto adequado de ESPAÇO (O (1)) = TIME (O (1)).
9119 Jeff Jeff
15
@ Jeff: Os computadores também são dispositivos físicos e, portanto, finitos. Ainda pensamos que as classes de complexidade nos ajudam a entender os computadores (embora não de maneira inequívoca, a saber, as muitas discussões sobre "e se P = NP, mas o expoente ou as constantes são enormes"). Por outro lado, o poder de um indivíduo aumenta computador em uma escala de tempo muito mais rápido do que o poder de um cérebro indivíduo ...
Joshua Grochow
4
Acho que foi Punya Biswal que surgiu com esta piada: a razão pela qual temos um tempo difícil chegar com funções rígidos explícitas é que nossos cérebros não são poderosos o suficiente para imaginar tais funções :)
Arnab
3
Joshua: Os cientistas da computação teóricos não estudam computadores; estudamos abstrações matemáticas de computadores. Dê-me uma abstração matemática de um cérebro humano e você provavelmente responderá sua própria pergunta.
Jeffε

Respostas:

17

Não afirmo que essa seja uma resposta completa, mas aqui estão alguns pensamentos que, esperançosamente, estão na linha do que você está procurando.

n

As pessoas geralmente parecem se dar bem com instâncias finitas de quebra-cabeças NP-completos, e ainda as consideram não triviais o suficiente para serem divertidas. As instâncias finitas de jogos PSPACE-completos que jogamos são consideradas algumas das tarefas intelectuais mais difíceis desse tipo. Isso pelo menos sugere que o PSPACE está "atingindo os limites superiores" de nossas habilidades. (No entanto, nossos oponentes nesses jogos completos do PSPACE geralmente são outras pessoas. Mesmo quando os oponentes são computadores, os computadores não são opostos perfeitos. Isso se encaminha para a questão do poder das provas interativas quando os jogadores são limitados computacionalmente. também o tecnicismo de que algumas generalizações desses jogos são EXP-completas em vez de PSPACE-completas.)

Até certo ponto, os tamanhos de problemas que surgem em quebra-cabeças / jogos reais foram calibrados de acordo com nossas habilidades. Sudoku 4x4 seria muito fácil, portanto chato. O Sudoku 16x16 levaria muito tempo (não mais do que a vida útil do universo, mas mais do que as pessoas geralmente estão dispostas a sentar para resolver um quebra-cabeça do Sudoku). 9x9 parece ser o tamanho "Goldilocks" para as pessoas que resolvem o Sudoku. Da mesma forma, jogar Free Cell com um baralho de 4 naipes de 13 cartas cada e 4 células livres parece ser a dificuldade certa de ser solucionável e desafiador para a maioria das pessoas. (Por outro lado, uma das pessoas mais inteligentes que conheço é capaz de resolver jogos de celular grátis como se estivesse contando números naturais "1,2,3,4, ..."). Da mesma forma, para o tamanho de Go and Chess Pranchas.

Você já tentou calcular uma permanente 6x6 à mão?

<1010

Por outro lado, para problemas no EXP, qualquer tamanho de problema abaixo do "calcanhar do exponencial" tem uma chance de ser solucionável pela maioria das pessoas em quantidades razoáveis ​​de tempo.

Quanto ao resto do PH, não há muitos (naturais?) Jogos naturais que as pessoas jogam com um número fixo de rodadas. Isso também está de alguma forma relacionado ao fato de não termos muitos problemas naturais completos para níveis de PH acima do terceiro.

Como mencionado por Serge, o FPT tem um papel a desempenhar aqui, mas (acho) principalmente pelo fato de que alguns problemas naturalmente têm mais de um "tamanho de entrada" associado a eles.

Joshua Grochow
fonte
13

A tese da Cognição Tratável postula que as capacidades cognitivas humanas são limitadas pela tratabilidade computacional. Dessa forma, a tese da P-Cognição usa o tempo polinomial determinístico como modelo para a rastreabilidade computacional, enquanto no artigo abaixo, argumenta-se que a tese da FPT-Cognição é mais apropriada. Veja o artigo de Iris van Rooij na edição de junho de 2009 do Parameterized Complexity Newsletter para uma discussão mais detalhada e sugestões para outros trabalhos.

Serge Gaspers
fonte
Existe alguma evidência de que isso é verdade?
yters
13

Penso que alguém é levado ao modelo errado, tentando extrapolar do tipo de coisas que o cérebro humano parece computar, e acho que seria melhor adotar a visão oposta e, em vez disso, extrapolar do modelo computacional que é.

TC0

Além disso, não concordo com a afirmação na pergunta de que a mente humana pode simular uma máquina de Turing. Em vez disso, o que ele pode fazer é simular o controle finito da máquina de Turing. Para executar tarefas muito complicadas, parece necessário poder gravar informações em uma "fita".

Kristoffer Arnsfelt Hansen
fonte
2
Com relação à simulação humana de uma MT ... eu estava assumindo que os seres humanos têm recursos razoáveis, como lápis e papel. Seu ponto é justo, no entanto.
Philip White
3
TC0TC0AC0
4
Escrever os fatos é sem dúvida uma das principais razões pelas quais progredimos como seres humanos e talvez também tenha causado a evolução do nosso cérebro. No mínimo, isso nos permite construir uma base sobre a qual construir nossas idéias (por exemplo, imagine se o TCS ou qualquer outro campo fosse baseado apenas na fala). Por esse motivo, acredito que se você remover a capacidade humana de "lápis e papel", poderá remover a fita da TM e reduzi-la a uma simples máquina finita.
chazisop
2
AC0
2
Ponto justo. Suponho que se a NEXP pudesse ser calculada a partir de circuitos "simples", isso seria uma evidência bastante forte de que um cérebro composto por neurônios "simplesmente simples" poderia realmente ser bastante poderoso, o que concorda com a nossa experiência. OTOH, acho que o circuito do cérebro tem profundidade muito maior que 3 :).
Joshua Grochow
10

As classes de complexidade são definidas em termos de complexidade assintótica, portanto, elas não mapeiam bem as habilidades cognitivas dos seres humanos, que são necessariamente limitadas a tamanhos de problemas limitados.

A regra geral é: se algo é fácil para um computador, pode ser difícil para um ser humano, vice-versa, se é difícil para um computador, pode ser fácil para um ser humano.

Aqui "fácil / difícil para um computador" refere-se à tratabilidade prática, não a uma classe de complexidade abstrata.

Por exemplo, adicionar uma lista de 1 bilhão de números inteiros é fácil para um computador moderno e difícil para um ser humano, enquanto a produção de uma descrição verbal de uma imagem é fácil para um ser humano, mas difícil (atualmente impossível no caso geral) para um computador.

A pesquisa de Inteligência Artificial mostrou que muitas tarefas cognitivas que seres humanos e animais realizam com facilidade, em alguns casos até subconscientemente, podem ser modeladas como problemas difíceis de PN. Os humanos não conseguem encontrar soluções ótimas para esses problemas para todos os tamanhos, mas conseguem encontrar soluções heurísticas para tamanhos práticos muito melhores do que os algoritmos de IA mais conhecidos.

Observe também que a distinção entre cérebro esquerdo e cérebro direito mencionada é muito simplista e obsoleta. A lateralização das funções cerebrais é muito mais sutil e pode até variar de um indivíduo para outro.

Antonio Valério Miceli-Barone
fonte
11
+1 para o primeiro parágrafo, -1 para todo o resto. MUITAS tarefas são fáceis para humanos e computadores, e MUITAS outras tarefas são difíceis para ambos.
9111 Jeff Jeff
11
Eu achava óbvio que existem tarefas triviais fáceis para humanos e computadores. De qualquer forma, estou atualizando minha resposta para torná-la mais explícita.
Antonio Valerio Miceli-Barone
2

Se optarmos por estudar o próprio cérebro humano, e não como os humanos o usam para resolver problemas, não acredito que seja uma questão de complexidade, mas de computabilidade. Como toda MT precisa de uma função de transição, um humano pode imitar os passos da MT, portanto, o cérebro humano está completo em Turing.

Na direção inversa, as TMs podem calcular tudo o que os humanos fazem? A resposta curta é que não sabemos. Supondo que a tese de Church-Turing seja verdadeira, se a resposta mudará ou não, depende da sua visão do mundo (filosófica, espiritual, religiosa e outras). Nesse caso, podemos dizer com segurança que o próprio cérebro humano, como parte do mundo material, pode ser simulado por uma máquina de Turing. O resto está em debate e, pelo menos na minha opinião, não está relacionado ao TCS.

PNPNPP1010100nn2log1010100vezes mais informações em todas as etapas do algoritmo acelerado. Obviamente, seria necessário um limite inferior específico para garantir que um algoritmo mais rápido (constantes incluídas) não existisse.

Portanto, se você deseja calcular com precisão quais problemas o cérebro humano, dadas as restrições da vida real, como distrações, atenção, etc., você deve ter um limite superior no número de etapas executadas no total, um limite superior no número de etapas executadas consecutivamente (mesmo o pesquisador mais dedicado deve dormir e comer), uma limitação do espaço (não apenas na fita, mas também em quaisquer registros "internos"), uma simulação de como a memória age porque, diferentemente das TMs, podemos esquecer algo que escrevemos em nossa "fita de trabalho" ou o estado exato e, é claro, determinar a relação entre as etapas do tempo da máquina e o tempo em segundos ou "etapas do cérebro humano". Talvez outras questões surgissem como você faria. Numa reviravolta irônica, talvez um ou mais desses problemas não possam ser resolvidos pelo cérebro humano, pelo menos com eficiência.

chazisop
fonte
Supondo que um humano tenha memória finita, ele não está completo. No máximo, ele pode simular máquinas de estado finito arbitrárias, até um certo tamanho. Um humano imortal com infinito papel, lápis e paciência seria Turing completo.
Antonio Valerio Miceli-Barone
@ user1749, sim, essa é realmente a ideia. Se você gostaria de ver o cérebro humano como ele é e não porque está vinculado a um ser humano, os computadores estão completos, mas têm uma vida útil muito menor que a de qualquer ser humano. Estou certo de que uma MT física também não duraria milênios.
chazisop
2

ThC0PNC#P

Ben Standeven
fonte
-1

Se você der a um ser humano um lápis e papel, ele poderá resolver praticamente qualquer problema, agindo como uma máquina. Então eu acho que isso não pode ser o ponto.

Quando o pensamento humano é abstração, ou seja, os seres humanos não administram as coisas (em primeiro lugar), eles criam pontos de vista sobre as coisas. Embora, como devo admitir, não possa fornecer uma teoria quase pronta para usar a abstração.

| =

modelpractice
fonte
-1

Estou pensando nessa questão há muito tempo. É a isso que cheguei:

nós, humanos, pensamos geralmente em objetos mentais abstratos e não em algoritmos. Os números que conhecemos, a língua que falamos, o pensamento já foram uma idéia abstrata. Essas idéias foram estendidas por filósofos, cientistas e depois colocadas em uso. O que temos é diferente de como eles se originaram.

Sua pergunta - "Qual classe de complexidade captura com mais precisão a totalidade do que os seres humanos podem realizar com suas mentes?" só pode ser respondida se houver prova suficiente de que os seres humanos sigam modelos matemáticos / algorítmicos / probabilísticos. Bem, eles podem seguir cada um dos itens acima ou combiná-los. Mas eles são realmente algo diferente. Este é apenas o pensamento humano normal. Quebrar os pensamentos criativos como a composição de Mozart, um poema ou o pensamento de um esportista nas respectivas formas formais (métodos matemáticos / lógicos de seu pensamento) e tentar generalizar seria uma façanha, mas não tenho certeza se isso será possível.

Também acho que podemos aproximar a classe de complexidade, mas nunca podemos ter certeza.

spiralarchitect
fonte