Vorlesung: Algorithmische Abstrakte Algebra (Computational Group Theory, Universal Algebra and CSPs, GAP)
LVA-Leiter: Peter Mayr
Montag, 10:15-11:45 Uhr, MT 130
1. Termin 21.10.2013, zusatzliche Termine Mittwoch, 23.10. und 30.10, 10:15-11:45 Uhr, SP2 416-2
How can we solve Rubik's cube? How many moves are necessary? How can we represent and work with innite groups on a computer? Is it possible to color a given map with four colors such that adjacent countries have distinct color? What is the connection between nding such a coloring, searching a database, and solving a system of linear equations? Which of these problems is hard, which one easy? In this course we will consider and formulate these questions as algebraic problems. In particular we study algorithms for computing with groups and more general algebraic structures. Our motivation for this comes from two areas:
- Concrete questions about concrete algebras: For example, what is the size of a permutation group given by a list of generators?
- Complexity theory: A number of classical decision problems like satisability of Boolean formulas, graph colorability, solving systems of linear equations ... can be formulated as Constraint Satisfaction Problems (CSP). An open conjecture in theoretical computer science states that every such CSP is either solvable in polynomial time (like solving linear equations) or NP-complete (like coloring graphs). Some recent progress on this question is due to algebraic methods. For every CSP one can construct an algebraic structure such that solving the CSP amounts to determining the intersection of subalgebras. Hence algorithms for computing with general algebraic structures are then applicable to these decision problems.
Computational Group Theory:
- Permutation groups: Sims stabilizer chains, strong generators
- Finitely presented groups: word problem, subgroup presentations, coset enumeration
Algebraic approach to CSP:
- Formulating CSPs via algebraic structures
- Polynomial time algorithms for CSPs: local consistency checking, bounded width, few subpowers
- Holt, Eick, O'Brien: Handbook of Computational Group Theory
- Hulpke: Notes on Computational Group Theory (external link: http://www.math.colostate.edu/~hulpke/)
The lectures will be blocked in order not to overlap with the workshops of the Special Semester on Applications of Algebra and Number Theory. The precise dates will be determined in the 1st meeting.