Modeling symmetries in human problem solving and problem space homomorphisms

In procedural knowledge space theory (PKST), the family of solutions for a given problem is called a "problem space''. The knowledge of a problem solver is represented as a specific subset of a problem space that satisfies the "sub-path assumption". Different types of ``symmetries'' could be found in a problem space that make certain parts of it ``equivalent''. These equivalence relations are introduced here as a homomorphism of one problem space into another problem space. Two types of homomorphisms are examined, which are named the ``strong'' and the ``weak homomorphism''. The former corresponds to the usual notion of ``operation preserving mapping''. The latter preserves operations in only one direction. The practical application of the proposed approach is presented through an empirical application with the Tower of London (TOL) test. A problem of the TOL consists of matching an initial configuration (i.e., a spatial disposition of colored balls on the pegs) with a goal configuration using the minimum number of moves. Due to the physical features of the TOL, several "symmetries" can be hypothesized. The introduction of symmetries leads to the construction of a problem space that is homomorphic to the original one. In particular, the homomorphic problem space is usually simpler and more abstract than the original one. Different symmetries hypothesis lead to different problem spaces which were empirically validated and compared with one another. The results of the empirical study are presented and discussed.