Proceedings of the Annual Meeting of the Cognitive Science Society

Previous studies have found that for electronic computers the computational requirements of solving an instance of aproblem are related to a specific set of features of the problem. This mapping has been shown to apply to electroniccomputers on a multitude of problems and is referred to as Instance Complexity (IC). However, it remains an open questionwhether IC applies to humans. For this purpose, we ran a set of experiments in which human participants solved a setof instances of one of three, widely studied, computational problems (Knapsack, Traveling Salesperson and the BooleanSatisfiability). 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.