Humans are exceptionally good at solving certain NP-hard or NP-complete problems
While humans can use heuristics and collective problem-solving to tackle certain complex combinatorial tasks efficiently, experimental studies show that their performance drops significantly as problem difficulty increases, indicating they do not inherently solve NP-hard problems exceptionally well compared to optimized algorithms.
The retrieved literature presents a nuanced picture. Some papers (e.g., [0], [7]) show that humans possess strong heuristic capabilities that can aid in solving or navigating NP-hard problems (like TSP and multiple sequence alignment), especially in human-in-the-loop or crowdsourced settings. Conversely, other studies (e.g., [8], [9]) demonstrate that human performance decreases when tackling hard instances or multilevel/higher-dimensional routing problems, and that increased effort does not fully compensate for computational hardness. Thus, humans are not exceptionally good at solving these problems in an absolute sense, though they employ effective heuristics—making the verdict CONTESTED.
The evidence we hold leans evenly split
How this was weighed
official record 3x · fact-check 2x · hedged 1x · crowd & reference 1x
- A glass-box interactive machine learning approach for solvin · peer-reviewed · supports · weight 1.6 · 2017
- Playing the System: Can Puzzle Players Teach us How to Solve · peer-reviewed · supports · weight 1.05 · 2023
- Is Hardness Inherent in Computational Problems? Performance · peer-reviewed · refutes · weight 1.05 · 2020
- Human Navigation in a Multilevel Travelling Salesperson Prob · peer-reviewed · refutes · weight 1.05 · 2022
Andreas Holzinger, M. Plass, K. Holzinger, G. Crişan, Camelia-M. Pintea, V. Palade. A glass-box interactive machine learning approach for solving NP-hard problems with the human-in-the-loop. 2017. https://doi.org/10.37193/cmi.2019.02.04
Human intuition and heuristic selection can successfully reduce the search space and complexity of NP-hard problems when integrated into human-in-the-loop machine learning.
Nitin Yadav, Carsten Murawski, Sebastian Sardiña, P. Bossaerts. Is Hardness Inherent in Computational Problems? Performance of Human and Electronic Computers on Random Instances of the 0-1 Knapsack Problem. 2020. https://doi.org/10.3233/FAIA200131
While humans recognize instances of NP-complete problems that are difficult for computers, increased cognitive effort does not allow them to overcome computational hardness.
See more details
Renata Mutalova, Roman Sarrazin-Gendron, Eddie Cai, Gabriel Richard, Parham Ghasemloo Gheidari, Sébastien Caisse, R. Knight, M. Blanchette, Attila Szantner, J. Waldispühl. Playing the System: Can Puzzle Players Teach us How to Solve Hard Problems?. 2023. https://doi.org/10.1145/3544548.3581375
Collective problem-solving and puzzle-playing by millions of humans can generate solutions to complex NP-hard biological sequence alignment tasks that rival standard algorithmic approaches.
P. Mavros, M. V. van Eggermond, C. Hoelscher. Human Navigation in a Multilevel Travelling Salesperson Problem. 2022. https://doi.org/10.31234/osf.io/4sv5w
Human performance in spatial optimization tasks like the traveling salesperson problem falls short of optimal combinatorial algorithms, especially as complexity and dimensionality increase.
The paper trail · every fact has a biography
Challenge the receipt
Citation formatting by citeproc-js (Frank Bennett) and the Citation Style Language project. Source and licenses.
Terms · Privacy · How verdicts work · Dispute this receipt