研究有關群論計算的多項式時間的算則是近廿年才開始，它的基本結果皆是Sims、Fu
rst、Hopcroft 和Luks所得到。自從「若群相交的問題是在P ，則圖形同構亦是」的
觀點獲證實，有關群論多項式時間算則的研究形成一股熱潮，到1982 Hoffmann 將以
前的結果彙集成冊，近些年來Butler、Cannon、Kantor和Luks都有有關置換群的論文
發表，本篇論文引用Kantor論大中「若G 為可解群，則G 的Sylow γ－子群和Hallπ
－子群皆可在多項式時間找到」的定理，將一冪零群與可解群的結果做了一些推進，
冪零群可說是介於可換群與可解群之間，換另一個角度而言，它是廣義的γ群。在19
85 Lipman 得到「若一個連接圖的自同構群為一可遷冪零群，則這圖形有Hamiltonia
n 路徑」，由此可見冪零群與圖論有相當密切的關係。
本文主要證明下列兩個結果：
定理A ：設置換群F、G<Sn 的生成集皆為已知，且其中之一為冪零群；則決定F∩G的
生成集是多項式時間。
定理B ：設可解置換群F<Sn的生成集為已知；則找一組Sylow ri- 子群Si，1<i<m ，
使得F=S1 S2…Sm 是多項式時間。
|