Monthly Archives: November 2017

Symmetries Part I

Finding symmetries is often essential for solving a problem. However, it is necessary to specify what is meant by “symmetry”, to indicate how one can find them, and finally to show what they are used for.

There are several kinds of symmetries. I am only interested here in symmetries that are associated to a permutation of the unknowns of a problem: when each unknown is replaced by the corresponding unknown in the permutation, both sets of constraints are identical. For every solution, one has immediately a symmetrical solution when one gives to each unknown the value of its corresponding unknown in the permutation. Therefore, for each solution, one also has as many new solutions as there are symmetries. In CAIA surprised me Part II, we have seen that CAIA had found 47 symmetries for a magic cube problem: every new solution generates 47 symmetrical solutions. Now, we will see how finding symmetries is useful for solving problems.

The first reason is that it considerably decreases the number of solutions that one has to find: for the magical cube, the number of solutions we are seeking is divided by 48. Moreover, symmetrical solutions are usually no longer interesting when one has found one of them, the user considers them equivalent; one only indicates their number. However, when there is no evident geometrical interpretation, it is sometimes difficult to see that two solutions are symmetrical: giving them is not always a complete waste of time. Naturally, CAIA adds constraints to the problem formulation so that it does not generate its symmetrical solutions. This is useful since the more a problem is constrained, the easier it is easy to solve.

The second reason is that it makes the search for new constraints easier: when one has found a constraint, all the constraints generated by the symmetries are also true. For example, with the magic cube problem, the main step in its successful resolution was the discovery on one constraint with only three unknowns: F(13)+F(14)+F(15)=42. A combinatorial search is more efficient with constraints with three unknowns rather than with constraints with 10 unknowns, which happens for all the constraints on the definition of this problem. Therefore, it is possible to apply the 47 symmetries already found. Two of them immediately give a constraint: F(11)+F(14)+F(15)=42 and F(5)+F(14)+F(23)=42. Unfortunately, one has not 47 new constraints: all the other symmetries give one of these three constraints. Without this, it is not evident that the system could also find the last two constraints: it does not consider all the possible derivations and, in any case, that would require much more time.

The third reason was a pleasant surprise. I did not expect it: CAIA could solve some problems after finding their symmetries, while it did not find any solution when it did not search for them before. The explanation is that it happens that the only (or the easiest) way to prove the goal is using a proof by cases. However, difficult decisions have to be made in order to define the constraints that define subsets of the possible values of the unknowns. Fortunately, symmetries offer these constraints on a plate: they have been added so that CAIA finds only one symmetrical solution. Moreover, usually, for a proof by cases, one must successively consider all the cases; it is sufficient to consider one of the cases! I have no room to explain this here, but I will give an example in the following post: CAIA easily finds all the solutions of a particular problem when it has discovered its symmetries; otherwise, it finds nothing.

Unfortunately, besides these positive points, sometimes there is a drawback: too many symmetries. One can waste a lot of time for finding them. This may happen when a problem has billions of solutions; it may also have millions of symmetries. In that situation, finding symmetries have no interest; the difficulty is to find at least one solution.

Searching for symmetries is a small, but important, part of CAIA. This is a meta-problem, that is a problem helping to solve other problems. Therefore, it is an important step in the bootstrap: CAIA finds symmetries, and this improves its performances. It was not necessary to write new modules for finding symmetries. It was sufficient to define the problem of finding symmetries in the same way as the other problems submitted by the users.