Computer Science and Problem Solving: New Foundations

Dagstuhl Seminar

Date: 28th of August - 2nd of September 2011

---

Organizers:

Georg Gottlob (University of Oxford, GB)
Yll Haxhimusa (Vienna University of Technology, Vienna, AT)
Zygmunt Pizlo (Purdue University - West Lafayette, US)
Iris van Rooij (Radboud University Nijmegen, NL)

Please find the final report of the Seminar [pdf]

Description:

Computer science has played a defining role in laying the foundations for cognitive psychology in the 1950s. Theories of computing at that time have had major impact on how psychologists have conceptualized the cognitive processes underlying human problem solving (e.g., through the seminal work of Allen Newell and Herbert Simon), and this impact continues even to this day. Yet, recent developments in problem solving research have also unveiled some limitations of classical approaches to problem solving and it seems that fundamentally new computational ideas are needed in order to move the field of problem solving forward. For instance, the classical idea of 'problem solving as search through a search space' can perhaps explain the difficulty of some problems (e.g., problems that are hard because they have intrinsically complex search spaces, such as NP-hard problems), but it seems unable to explain the difficulty of a whole class of other important problems (e.g., problems for which 'solving' means 'correctly representing'). For the latter class of problems, once the right representation has been formed, solving the problem is easy. This observation raises several questions:

• How can we explain the process of building up a problem representation? Can we explain it computationally?
• Can we explain why, and predict when, finding the right representation is difficult, and when it is easy?
• Can we build a computational theory for different classes of 'representational complexity', analogous to existing classes of 'computational complexity'?
• Can the notions of computational complexity and representational complexity possibly be reconciled by a unifying theory of problem solving?

There are many different ways to approach the notion of 'representational complexity'. One idea is that a problem is difficult if the problem solver unintentionally has settled on a wrong representation and is unaware of this or otherwise unable to let go of the wrong representation in order to find a better one (the notion of 'fixedness' in cognitive psychology expresses this idea). Another idea is that a problem is difficult if the problem solver knows that the current representation is faulty, but finding a better representation requires (potentially sequentially) choosing from a (potential indefinite) set of re-representation operators (this idea is pursued in the domain of analogical problem solving). Yet, another idea is that a problem is difficult if it does not allow for a representation that affords efficient search of the problem space (this idea has connections to theories of data structures and their relationship with computational efficiency).
This seminar aims to bring together computer scientists and psychologists to exchange ideas, models and experimental data on human and artificial problem solving. The primary aim of the seminar is to inspire new formal approaches to 'representational complexity' and to build a research agenda for advancing our understanding of the role of 'representation' in human and artificial problem solving. Attendees are invited to present their own research and explore opportunities for new collaborations. After the completion of the seminar, all participants will be invited to submit their presented work for publication in a special issue of the Journal of Problem Solving (see http://docs.lib.purdue.edu/jps/).
The seminar welcomes researchers from a wide variety of research areas, including, but not limited to, the following.
Keywords:
Computer science:graph theory, topology, geometry, logic, computational complexity, descriptive complexity
Psychology: cognitive modeling, heuristics, insight, visual problem solving, analogical problem solving, creativity, education.

Final Report

[Computer Science & Problem Solving: New Foundations]