•  
  •  
 

Abstract

When computer scientists discuss the computational complexity of, for example, finding the shortest path from building A to building B in some town or city, their starting point typically is a formal description of the problem at hand, e.g., a graph with weights on every edge where buildings correspond to vertices, routes between buildings to edges, and route-distances to edge-weights. Given such a formal description, either tractability or intractability of the problem is established, by proving that the problem either enjoys a polynomial time algorithm or is NP-hard. However, this problem description is in fact an abstraction of the actual problem of being in A and desiring to go to B: it focuses on the relevant aspects of the problem (e.g., distances between landmarks and crossings) and leaves out a lot of irrelevant details.

This abstraction step is often overlooked, but may well contribute to the overall complexity of solving the problem at hand. For example, it appears that “going from A to B” is rather easy to abstract: it is fairly clear that the distance between A and the next crossing is relevant, and that the color of the roof of B is typically not. However, when the problem to be solved is “make X love me”, where the current state is (assumed to be) “X doesn’t love me”, it is hard to agree on all the relevant aspects of this problem.

In this paper a computational framework is presented in order to formally investigate the notion of relevance in finding a suitable problem representation. It is shown that it is in itself intractable in general to find a minimal relevant subset of all problem dimensions that might or might not be relevant to the problem. Starting from a computational complexity stance, this paper aims to contribute a computational framework of ‘relevancy’ in problem solving, in order to be able to separate ‘easy to abstract’ from ‘hard to abstract’ problems. This framework is then used to discuss results in the literature on representation, (insight) problem solving and individual differences in the abstraction task, e.g., when experts in a particular domain are compared with novice problem solvers.

Download

Share

COinS