Decomposition and Problem-Solving

2022-05-28 • 4 min read

Everyone knows it’s easier to solve a complex problem if you break it up into simpler subproblems. This is called decomposition and it works in many domains. For example:

As a rule, it’s easier to solve a series of simple subproblems than it is to solve one big complex problem directly. The argument:

  1. Any problem has a set of possible solutions and non-solutions – this is the search space. When trying to solve a problem, we are searching this space for promising solutions.
  2. The size of a problem’s search space is the product of the sizes of the subproblems’ search spaces.
  3. Therefore, decomposing the problem will result in a non-linear reduction in size of the spaces we search in.

I know that sounds abstruse, so here is an example, a basic decision-making problem. Say I am trying to pick a restaurant for the anniversary dinner of my wife and myself. Suppose there are 7,000 restaurants in Berlin. That’s a pretty large search space. But I can split the problem into three subproblems:

  1. In which district do we want to eat?
  2. Which style of cuisine do we want to eat?
  3. Given a district and a cuisine, at which restaurant do we want to eat?

Berlin has 12 districts, and let’s say I divide all restaurants into 20 types of cuisine. That leaves an average of 7,000 ÷ 12 ÷ 20 = 29 restaurants for each combination of cuisine and district. Now, instead of trying to solve a problem with 7,000 possible answers, I solve first one with 12 possibilities, then one with 20 possibilities and finally one with (on average) 29 possibilities. That’s much more manageable. We could even look through all 29 possibilities to see which one we like more.

img

(Of course we usually only do something like this – we rarely make an exhaustive search, or split up problems consciously and deliberately – but the idea should be essentially the same; the difference is one of degree, and the difficulty of and time needed for any search are generally more substantial when the size of the search space is larger, and vice versa.)

These are some ways in which decomposition can lead to suboptimal answers:

That means: Each subproblem should separate the search space into exhaustive, mutually exclusive and balanced parts.

Problem decomposition may be an example of the representational change theory of insight (Knoblich et al. 1999). The representational change theory says that we can make progress on a problem by viewing it differently. Decomposing a problem is one way of viewing it differently.[1] We can get stuck in a search space, and decomposition allows us to move to a fresh space, where we are not anchored to any particular area.

References #

Knoblich, Günther, Stellan Ohlsson, Hilde Haider, and Detlef Rhenius. 1999. “Constraint Relaxation and Chunk Decomposition in Insight Problem Solving.” Journal of Experimental Psychology: Learning, Memory, and Cognition 25 (6): 1534–55. https://doi.org/10.1037/0278-7393.25.6.1534

Footnotes #

  1. Another way brought up in Knoblich et al. (1999) is constraint relaxation. That means something like “thinking outside the box”. In my restaurant example, it might have entailed considering restaurants outside Berlin, or considering eating in, etc. ↩︎