-4
$\begingroup$

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:

https://www.americanscientist.org/article/candy-crushs-puzzling-mathematics

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.

$\endgroup$
11
  • $\begingroup$ (i) Outperform by what metric? (ii) What is a "provably optimal approximation algorithm"? $\endgroup$
    – Neal Young
    Sep 21 at 0:56
  • $\begingroup$ (i) finding better solutions in a shorter amount of time (ii) I understand for some np-hard problems we know how well the best polynomial approximation algorithm performs, like with set cover I think the greedy algorithm has been proven the optimal polynomial approximation algorithm. $\endgroup$
    – yters
    Sep 21 at 2:20
  • $\begingroup$ If the downvoters could explain what is wrong with the question, I can improve it, or I can move it to a different site if there is a more appropriate site. I asked a similar question 10 years ago, but this is more specific to NP-hard problems as I am not interested in Captcha sorts of answers. $\endgroup$
    – yters
    Sep 21 at 12:19
  • 1
    $\begingroup$ Section 2.7.2 of the Arora-Barak text points out that for most known axiomatic systems (e.g. Peano arithmetic or Zermelo-Fraenkel Set Theory) proofs can be verified in time polynomial in their length, and that the set of provable statements is easily shown to be NP-complete. On the other hand, people seem to be better than computers at figuring out whether statements are provable. So perhaps this is, loosely speaking, the kind of thing you are looking for. I don't think it's been studied formally though. $\endgroup$
    – Neal Young
    Sep 24 at 14:44
  • 1
    $\begingroup$ The question might be better suited to cognitive science. See, for example, this paper by Iris Van Rooij, which discusses the P-cognition thesis and the FPT-cognition thesis: doi.org/10.1080/03640210801897856 $\endgroup$ Sep 29 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.