Cognitive Sciences Stack Exchange is a question and answer site for practitioners, researchers, and students in cognitive science, psychology, neuroscience, and psychiatry. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It has been noted that humans are good at solving the travelling salesmen problem under certain constraints. Are there other NP-hard or NP-complete problems that human beings are good at solving? Has there been other research (psychological, neurobiological) on this?

One lead I'm currently investigating is how humans are good at playing Minesweeper, despite the fact that is it is NP-Complete.

share|improve this question
Strongly related:… – user6682 Sep 23 '14 at 12:06
up vote 1 down vote accepted

With regard to the relationship between the brain and complexity theory, I think it's important to remember that the brain hardly ever comes up with exact solutions to problems and seems to prefer inductive reasoning to deduction. (How to induce a minesweeper strategy computationally) Furthermore, we mostly conjure up approximations. Précis of Bayesian Rationality: The Probabilistic Approach to Human Reasoning discusses problem solving in inexact (probabilistic) terms. I believe that one of the follow-up articles (Identifying the optimal response is not a necessary step toward explaining function, page 85) is relevant to your question:

"An explanation requiring an optimal response function must also consider that: (e) for problems of inductive inference, the optimal response is often analytically intractable to determine with exact methods, and will not be unique; (f) behavioral responses are typically approximately optimal, revealing a tendency rather than a correspondence"

share|improve this answer

Collective responses can be aggregated to combine common solution fragments into a global solution. Maybe a key to solve NP-hard/complete is having enough diversity, hence working in a collective sense. Check out The Wisdom of the Crowd in Combinatorial Problems, from Sheng Kung Michael Yi,a Mark Steyvers,a Michael D. Lee,a Matthew J. Dryb

share|improve this answer
Welcome to cogsci.stackexchange! This looks like the start of a really good answer! Would you mind elaborating on how collective responses can be aggregated? If you want further tips on making a good answer, check out "How do I write a good answer?" which I had to read a few times when I first joined the site. (: – Seanny123 Jul 25 '14 at 14:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.