Constraints programming as a tool to solve computational group theory problems
Problems often consist of choices. Making an optimal choice which is compatible with all other choices made is difficult. Constraint programming (CP) is the branch of Artificial Intelligence, where computers help us to make these choices.
Constraint programming is a multidisciplinary technology combining computer science, operational research and mathematics. Constraints arise in design & configuration, planning & scheduling, diagnosis & testing, and in many other contexts. CP can solve problems in telecommunication, e-commerce, electronics, bioinformatics, transportation, network management, supply chain management, and many other fields. My research is always very varied; I have looked at transport scheduling problems, satellite data processing problems and some problems from mathematics.
A constraint program consists of a set of variables, a set of possible values, for each variable and a set of constraints. For example, the problem might be to fit components (values) to circuit boards (variables), subject to the constraint that no two components can be overlapping. A solution to a CSP is an allocation of values to variables such that none of the constraints are violated.
Group theory is the mathematical study of symmetry. One may remember in primary school finding the symmetry of shapes, possibly by using a mirror putting it down on a line through the shape and seeing if the same shape can be seen through the mirror as was on the worksheet. If the same shape was seen than this line could label led as symmetry. Group theory is the science that allows you to reason about symmetry. By using group theory you can compare and contrast the symmetry found in one shape, with that in another shape. Group theory is used by physicists in a very similar way. They are interested in trying to build stable crystal structures, and they look for symmetries to help them towards this goal.
There are still a lot of open problems in group theory and it is widely studied by pure mathematicians. The goal of this project is to build a system using constraint programming that will allow researchers to learn more about group theory. I think this is an exciting project as it will show how a computer, can help a researcher to reason about a branch of science. I expect a lot of the time this system will actually be used to negate results. By this I mean that a group theorists will come up with a possible group theory
theorem, and wish to test whether it is valid. One way to do this, will be to ask the computer to look for groups (sets of symmetry) which do not satisfy the theorem, if the computer can find such an example then the theorem is false. Quite often scientists can spend weeks exploring a theorem or hypothesis only to find a counter example, and hence realise they were wrong (I have done this myself, on more than one occasion), I hope my program will save some of this time and effort. I also believe that once this system is developed for group theory it might be possible to develope similar system for other areas of mathematics and even other disciplines. I think this would be a very exciting innovation for the scientific community.
Funder: Dorothy Hodgkin Fellowship
Start Date: 01/08/2009
End Date: 30/10/2011
Research Themes:
For further information about the Constraints programming as a tool to solve computational group theory problems project please contact Dr Karen Petrie.