תורת החבורות החישובית

תורת החבורות החישובית היא ענף של מתמטיקה חישובית העוסק באלגוריתמים לפתרון בעיות הנובעות מתורת החבורות.

חישובים בחבורות אבסטרקטיות

בעיות רבות בחבורות נתונות על ידי יוצרים ויחסים אינן ניתנות לחישוב אלגוריתמי (ראו תכונת מרקוב ובעיות דן). עם זאת, יש שיטות (שאינן מבטיחות עצירה) לחישוב האינדקס של תת-חבורה בחבורה נתונה: ראו אלגוריתם טוד-קוקסטר ואלגוריתם קנות'-בנדיקס.

חישובים בחבורה הסימטרית

חישובים רבים בחבורות סופיות אפשר לממש בחבורת התמורות $\ S_{n}$ . החבורה נתונה בדרך כלל על ידי קבוצת יוצרים.

החישובים נעזרים בתת-חבורות המייצבים $G_{A}=\{g\in G:(\forall a\in A)\,g(a)=a\}$ של החבורה G. למשל, את סדר החבורה G אפשר לחשב על ידי הכפלת האינדקסים בשרשרת תת-החבורות $1=G_{1,\dots ,n}<G_{1,\dots ,n-1}<\cdots <G_{1}<G$ .

את החישוב הנאיבי אפשר להאיץ באמצעות שימוש בבסיסים: בסיס לחבורה G הוא קבוצת נקודות $B\subseteq \{1,\dots ,n\}$ המקיימת $G_{B}=1$ (ולכן איבר $g\in G$ מוגדר היטב על ידי הפעולה שלו על B). בסיס חזק לקבוצת יוצרים X הוא בסיס, המקיים את התנאי $G_{B'}=\langle X\cap G_{B'}\rangle$ לכל תת-קבוצה $\ B'\subseteq B$ . אלגוריתם שרייר-סימס מקבל קבוצת יוצרים לחבורת תמורות, ומחזיר קבוצת יוצרים טובה יותר ובסיס חזק ביחס אליה.