ECAI Conference 2020 Conference Paper
Is Hardness Inherent in Computational Problems? Performance of Human and Electronic Computers on Random Instances of the 0-1 Knapsack Problem
- Nitin Yadav
- Carsten Murawski
- Sebastian Sardiña
- Peter Bossaerts
Many cognitive problems people face have been shown to be computationally intractable. However, tractability is typically defined in terms of asymptotic worst-case behaviour of instances. One approach for studying typical cases of NP-complete problems is based on random instances. It has been shown that random instances of many NP-complete problems exhibit a phase transition in solvability and that hard instances tend to occur in this phase transition. Here, we characterise a phase transition in solvability for random instances of the 0-1 knapsack problem in terms of two simple instance properties. Subsequently, we show that compute time of algorithms peaks in the phase transition. Remarkably, the phase transition likewise predicts where people spend the most effort. Nevertheless, their performance decreases. This suggests that instances that are difficult for electronic computers are recognized as such by people, but the increased effort does not compensate for hardness. Given the ubiquity of the knapsack problem in every-day life, a better characterisation of the properties that make instances hard will help understand commonalities and differences in computation between human and digital computers, and to improve both decision environments (contracts, regulation) as well as human-computer interfaces.