I am interested in the comparison of human performance vs algorithmic performance on NP-hard problems, both with regard to exact solutions and approximations, with the intent to find areas where humans can definitively outperform provably optimal algorithms (exact or approximations).
Are you aware of any such research?
A fair amount of searching on Google scholar has not turned up anything obvious.
UPDATE: A bit more background as to why I am asking the question.
I asked a similar question 10 years ago: Human intelligence and algorithms
The difference between that question and this one is I want to avoid answers that refer to problems that humans can solve, but we have no idea whether someday computers will solve them. With NP-hard problems, unless NP=P which most computer scientists think is false, then we have a pretty good idea about the computational limits. Then, we can search the space of those problems to see if there are instances that are provably intractable for computers, while are still human solvable. If we find such instances, this would be a good indication that the human mind is somehow better than a deterministic Turing machine, perhaps a non-deterministic Turing machine or better. I hope that makes sense.
As to why I am asking on this forum, the question I asked 10 years ago was well received, and no one tried to shut down the question. I was hoping for a similar response second time around.
Finally, why even ask the question? I realize that NP-hard problems are not easy for humans in general. On the other hand, there is a lot of research showing many popular games are NP-hard. For example, Candy Crush:
So, it seems possible there is an inbetween set of NP-hard problem instances which are hard for computers yet easy for humans.
P.S. the author of the above article also has an interesting idea, that provides practical motivation for my question:
The idea of problem reduction offers an intriguing possibility for Candy Crush addicts. Perhaps we can profit from the millions of hours humans spend solving Candy Crush problems? By exploiting the idea of a problem reduction, we could conceal some practical computational problems within these puzzles. Other computational problems benefit from such interactions: Every time you prove to a website that you’re a person and not a bot by solving a CAPTCHA (one of those ubiquitous distorted images of a word or number that you have to type in) the answer helps Google digitize old books and newspapers. Perhaps we should put Candy Crush puzzles to similar good uses.