7

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.

Seanny123
  • 8,853
  • 3
  • 25
  • 61
  • 1
    Strongly related: http://cstheory.stackexchange.com/questions/5379/what-is-the-complexity-class-most-closely-associated-with-what-the-human-mind-ca –  Sep 23 '14 at 12:06
  • Another related question: https://cs.stackexchange.com/questions/47712/why-can-humans-solve-certain-undecidable-problems –  Aug 19 '19 at 16:11

2 Answers2

1

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"

0

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

Sofia Silva
  • 1
  • 6
    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