prip logo
Dagstuhl Seminar

Resource Bounded Problem Solving

Dagstuhl Seminar

Date: August 17 - 22, 2014, Dagstuhl Seminar 14341


Yll Haxhimusa, Vienna University of Technology, Austria
Iris van Rooij, Radboud University, The Netherlands
Shashank Varma, University of Minnesota, USA
Todd Wareham, Memorial University of Newfoundland, Canada


In der Beschraenkung zeigt sich erst der Meister
It is in working within limits that the Master reveals himself
Johann Wolfgang von Goethe

Problem solving, whether by humans or machines, is bounded by the resources at hand. For machines, these resources fundamentally include hardware and processing speed. For humans, important resources also include mental representations, memory capacities, inferential capacities, and time to name a few. All these resources can be severely limited, by constraints imposed by both the implementing hardware (current technology in the case of machines, the organization of our brains in the case of humans) and the physical and social operating environments.
The study of resource-bounded problem solving has a long and productive history within computer sci- ence, which has resulted in a number of eficient exact-solution algorithms and algorithm design techniques as well as, where such algorithms are not possible, various widely-applicable approximate-solution heuristics. Given that brains have evolved to solve problems under severe resource constraints, resource-bounded prob- lem solving may also provide one of the best windows on the organization of cognitive brain function. Trying to model exactly how humans solve really hard|that is, resource demanding|problems eficiently seems a good strategy from the perspective of deriving predictive and explanatory cognitive models. After all, many cognitive models may be able to match human performance on really easy problems, but only a few can for really hard problems. Hence, if one finds even one cognitive model that can solve a hard problem as well as humans one can be much more confident that it captures fundamental principles of human cognition.
What makes tasks resource demanding? Here computational complexity theory is a key source of infor- mation for the study of human and machine problem solving. Computational complexity theory studies the intrinsic resource demands of various computational problems. It allows us to assess when resource demands are low, reasonable, high, or impractically high. Though the importance of computational complexity has been recognized in computer science for decades, it has been underutilized to date in psychology. This is not for want of opportunities, as cases are known where psychologists have studied principles of resource-bounded problem solving in apparent ignorance of relevant computational complexity results. The following example illustrates such a situation.
With this seminar we aim to stimulate the exchange of ideas and results between computational complexity theorists and psychologists studying problem solving. In particular, we want to ensure that this exchange is of use to both (and not just one) of these communities. The following is a list of questions to help stimulate and guide this exchange:
  • Why is resource-bounded problem solving so suboptimal on some occasions yet so successful on others?
  • Why are some problems that are dificult for machines very easy for humans, and vice versa? Could this be explained by humans and machines making different use of resources?
  • Are human brains optimized to use their resources in particular ways, which may support some types of problem solving but not others? How can we achieve similar ways of optimizing resource usage in machines?
  • Can new computational complexity theory be developed relative to resources other than time and space that are also relevant for studying resource-bounded human problem solving?
  • How can computational complexity theoretic predictions for cognitive models of resource-bounded problem solving be empirically tested?
  • How can cognitive models of resource-bounded problem solving interface with neural models of brain organization?
After the seminar, participants will be invited to publish their ideas in one or more peer reviewed special issues of The Journal of Problem Solving (see


August 17 - 22, 2014
© 2001-2012. Yll Haxhimusa. Last modified: April 03, 2013. Best viewed with Mozilla. Valid HTML 4.01 Transitional Valid CSS!