Computational cognitive requirements of random decision problems
- Juan Pablo Franco, University of Melbourne, Melbourne, Australia
- Karlo Doroc, University of Melbourne, Melbourne, Australia
- Nitin Yadav, University of Melbourne, Melbourne, Australia
- Peter Bossaerts, University of Melbourne, Melbourne, Australia
- Carsten Murawski, University of Melbourne, Melbourne, Australia
AbstractPrevious studies have found that for electronic computers the computational requirements of solving an instance of a problem are related to a specific set of features of the problem. This mapping has been shown to apply to electronic computers on a multitude of problems and is referred to as Instance Complexity (IC). However, it remains an open question whether IC applies to humans. For this purpose, we ran a set of experiments in which human participants solved a set of instances of one of three, widely studied, computational problems (Knapsack, Traveling Salesperson and the Boolean Satisfiability). We found that, in line with our hypothesis, IC had a negative effect on human performance in all problems. Our results suggest that IC can be used as a generalisable measure of the computational resource requirements of a task. Moreover, given its properties, IC could serve a crucial role in the cognitive resource allocation process.