Directed Research Project Details
Search Algorithms for Permutation Groups
| Author: | David Hofer |
|---|---|
| Date: | March 15, 2004 |
| Time: | 10:00 |
| Location: | 220 Deschutes |
| Committee: | Eugene Luks Matt Ginsberg Chris Wilson Charles Wright |
Abstract
When you can't solve a problem in polynomial time, what do you do? Search algorithms are a useful fallback for problems in computational group theory with no known efficient solution. We consider several such problems for permutation groups, beginning with SET STABILIZER and GROUP INTERSECTION, and describe an existing solution for each. The solutions use the same basic search algorithm on a permutation group, modified to include problem-specific pruning heuristics. We then use this algorithm in several ways to solve two problems, SUBSET TRANSPORTER and AUGMENTED CLAUSE RESOLUTION, which have applications in the area of boolean satisfiability. Finally, we focus on SET STABILIZER and the existing implementation of its solution in GAP, an open-source system for computing discrete algebraic problems. GAP implements the search algorithm for SET STABILIZER mentioned above. We show that the algorithm and its implementation take exponential time for a class of 2-groups. But algorithms exist which compute SET STABILIZER in polynomial time for the $\Gamma_d$ class of groups, which contains all 2-groups. Using ideas from one such algorithm, we indicate how GAP's algorithm may be modified to run in polynomial time for $\Gamma_d$ groups, without severely impacting its performance on other groups.