Computational cognitive requirements of random decision problems

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.

Return to previous page