Masalah kata untuk grup

masalah algoritmik untuk memutuskan apakah dua kata dalam generator mewakili elemen yang sama

Dalam matematika, terutama di bidang aljabar abstrak dikenal sebagai teori grup kombinatorial, masalah kata untuk grup yang dihasilkan secara hingga G adalah masalah algoritmik untuk memutuskan apakah dua kata dalam generator mewakili elemen yang sama. Lebih tepatnya, jika A adalah himpunan terbatas generator untuk G maka kata uji coba adalah masalah keanggotaan untuk bahasa formal dari semua kata dalam A dan sekumpulan formal invers yang memetakan identitas di bawah peta alami dari monoid bebas. Jika B adalah himpunan penghasil hingga lain untuk G , maka masalah kata di himpunan pembangkit B setara dengan masalah kata di atas himpunan pembangkit A . Jadi seseorang dapat berbicara dengan jelas tentang desidabilitas dari masalah kata untuk grup G yang dihasilkan secara tak terbatas.

Masalah kata seragam yang terkait tetapi berbeda untuk kelas K dari grup yang disajikan secara rekursif adalah masalah algoritmik dalam memutuskan, diberikan sebagai masukan presentasi P untuk grup G di kelas K dan dua kata di generator G , baik kata mewakili elemen yang sama dari G . Beberapa penulis mensyaratkan kelas K untuk didefinisikan oleh sekumpulan presentasi secara rekursif dapat dihitung.

Sejarah

sunting

Sepanjang sejarah subjek, komputasi dalam kelompok telah dilakukan menggunakan berbagai bentuk normal. Ini biasanya secara implisit memecahkan masalah kata untuk kelompok yang bersangkutan. Pada tahun 1911 Max Dehn mengusulkan bahwa masalah kata adalah bidang studi penting dalam dirinya sendiri,[1] bersama dengan masalah konjugasi dan masalah isomorfisme grup. Pada tahun 1912 ia memberikan algoritme yang memecahkan masalah kata dan konjugasi untuk grup fundamental dari manifold dua dimensi yang dapat diorientasikan tertutup dari genus yang lebih besar dari atau sama dengan 2.[2] Penulis selanjutnya telah memperluas Algoritma Dehn dan menerapkannya ke berbagai teori grup masalah keputusan.[3][4][5]

Hal ini ditunjukkan oleh Pyotr Novikov pada tahun 1955 bahwa terdapat kelompok G yang disajikan secara terbatas sehingga kata masalah untuk G adalah tidak dapat diputuskan.[6] Segera diikuti bahwa masalah kata seragam juga tidak dapat diputuskan. Bukti berbeda diperoleh oleh William Boone pada tahun 1958.[7]

Kata masalah adalah salah satu contoh pertama dari masalah yang tidak dapat diselesaikan yang tidak ditemukan di logika matematika atau teori algoritma, tetapi di salah satu cabang utama matematika klasik, aljabar. Sebagai hasil dari ketidakmampuannya, beberapa masalah lain dalam teori gruo kombinatorial telah terbukti tidak dapat diselesaikan juga.

Penting untuk disadari bahwa kata problem sebenarnya dapat dipecahkan untuk banyak grup G . Misalnya, grup polisiklik memiliki masalah kata yang dapat dipecahkan karena bentuk normal dari kata arbitrer dalam presentasi polisiklik mudah dihitung; algoritma lain untuk grup mungkin, dalam keadaan yang sesuai, juga memecahkan masalah kata, lihat Algoritma Todd-Coxeter[8] dan Algoritma penyelesaian Knuth–Bendix.[9] Di sisi lain, fakta bahwa algoritme tertentu tidak menyelesaikan masalah kata untuk grup tertentu tidak menunjukkan bahwa grup tersebut memiliki masalah kata yang tidak dapat diselesaikan. Misalnya algoritma Dehn tidak memecahkan masalah kata untuk grup fundamental dari torus. Bagaimanapun kelompok ini adalah produk langsung dari dua grup siklik tak hingga dan memiliki masalah kata yang dapat dipecahkan.

Penjelasan yang lebih konkrit

sunting

Dalam istilah yang lebih konkret, soal kata seragam dapat diekspresikan sebagai pertanyaan menulis ulang, untuk pita literal.[10] Untuk presentasi P dari grup G , P akan menentukan sejumlah generator

x, y, z, ...

untuk G . Kita perlu memperkenalkan satu huruf untuk x dan huruf lainnya (untuk kenyamanan) untuk elemen grup yang diwakili oleh x−1. Sebut huruf-huruf ini (dua kali lebih banyak dari generator) alfabet   untuk masalah kita. Kemudian setiap elemen di G diwakili dalam beberapa cara oleh produk

abc ... pqr

simbol dari  , dari beberapa panjang, dikalikan dengan G . String dengan panjang 0 ( string null) adalah singkatan dari elemen identitas e dari G . Inti dari keseluruhan masalah adalah untuk dapat mengenali semua cara e dapat direpresentasikan, dengan beberapa hubungan.

Efek dari relasi dalam G adalah membuat berbagai string tersebut mewakili elemen yang sama dari G . Sebenarnya relasi menyediakan daftar string yang bisa dikenalkan di tempat yang kita inginkan, atau dibatalkan setiap kali kita melihatnya, tanpa mengubah 'nilai', yaitu elemen grup yang merupakan hasil perkalian.

Untuk contoh sederhana, ambil presentasi {a | a3}. Menulis A untuk kebalikan dari a , kami memiliki kemungkinan string yang menggabungkan sejumlah simbol a dan A . Kapanpun kita melihat aaa , atau aA atau Aa kita mungkin mencoretnya. Kami juga harus ingat untuk mencoret AAA ; Ini mengatakan bahwa karena kubus a adalah elemen identitas G , begitu pula kubus dari kebalikan dari a . Dalam kondisi seperti ini kata soal menjadi mudah. Pertama kurangi string menjadi string kosong, a , aa , A atau AA . Kemudian perhatikan bahwa kami juga dapat mengalikan dengan aaa , sehingga kami dapat mengonversi A menjadi aa dan mengubah AA menjadi a . Hasilnya adalah bahwa masalah kata, di sini untuk grup siklik dari orde tiga, dapat dipecahkan.

Namun, ini bukan kasus yang khas. Sebagai contoh, kami memiliki bentuk kanonik tersedia yang mengurangi string apa pun menjadi satu string maksimal tiga, dengan mengurangi panjangnya secara monoton. Secara umum, tidak benar bahwa seseorang bisa mendapatkan bentuk kanonik untuk elemen, dengan pembatalan bertahap. Seseorang mungkin harus menggunakan relasi untuk memperluas pita berkali-kali lipat, untuk akhirnya menemukan pembatalan yang menurunkan panjangnya.

Hasilnya adalah, dalam kasus terburuk, bahwa hubungan antara string yang mengatakan mereka sama di G adalah Masalah yang tidak dapat diputuskan .

Contoh

sunting

Grup berikut memiliki masalah kata yang bisa dipecahkan:

Contoh dengan masalah kata yang tidak terpecahkan juga diketahui:

  • Diberikan himpunan yang dapat dihitung secara rekursif A dari bilangan bulat positif yang memiliki masalah keanggotaan yang tidak terpecahkan, ⟨a,b,c,d | anban = cndcn : nA⟩ adalah grup yang dihasilkan secara terbatas dengan presentasi yang dapat dihitung secara rekursif yang masalah katanya tidak terpecahkan[13]
  • Setiap grup yang dihasilkan secara terbatas dengan presentasi yang dapat dihitung secara rekursif dan masalah kata yang tidak terpecahkan adalah subkelompok dari grup yang disajikan secara terbatas dengan masalah kata yang tidak dapat larut[14]
  • Jumlah relator dalam kelompok yang disajikan secara terbatas dengan masalah kata yang tidak terpecahkan mungkin serendah 14 kali[15] atau bahkan 12 kali.[16][17]
  • Contoh eksplisit dari presentasi singkat yang masuk akal dengan masalah kata yang tidak terpecahkan diberikan dalam Collins 1986:[18][19]
 

Solusi parsial dari masalah kata

sunting

Masalah kata untuk grup yang disajikan secara rekursif dapat diselesaikan sebagian dalam pengertian berikut:

Diberikan presentasi rekursif P = ⟨X|R⟩ untuk grup G , tentukan:
 
lalu ada fungsi rekursif parsial fP yaitu:
 

Lebih informal, ada algoritma yang berhenti jika u = v , tapi tidak melakukannya sebaliknya.

Oleh karena itu, untuk menyelesaikan masalah kata untuk P cukup dengan membangun fungsi rekursif g sedemikian rupa sehingga:

 

Namun u = v di G jika dan hanya jika uv−1=1 di G . Oleh karena itu, untuk menyelesaikan masalah kata untuk P cukup dengan membangun fungsi rekursif h sehingga:

 

Contoh

sunting

Berikut ini akan dibuktikan sebagai contoh penggunaan teknik ini:

Teorema: Grup residual finit yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan.

Bukti: Seharusnya G = ⟨X|R⟩ adalah suatu grup yang terbatas sisa.

Misalkan S menjadi grup dari semua permutasi dari N, bilangan asli, yang memperbaiki semua kecuali banyak bilangan hingga:

  1. S adalah terbatas lokal dan berisi salinan dari setiap grup hingga.
  2. Masalah kata dalam S dapat dipecahkan dengan menghitung produk permutasi.
  3. Ada pencacahan rekursif dari semua pemetaan himpunan hingga X menjadi S .
  4. Karena G adalah residual finite, jika w adalah sebuah kata di generator X dari G maka w ≠ 1 dalam G jika dan hanya beberapa pemetaan X menjadi S menyebabkan homomorfisme sedemikian rupa sehingga w ≠ 1 pada S.

Dengan fakta-fakta ini, algoritma ditentukan oleh pseudocode berikut:

For setiap pemetaan X menjadi S
    If setiap relator di R puas di S
        If w ≠ 1 pada S
            return 0
        End if
    End if
End for

mendefinisikan fungsi rekursif h seperti itu:

 

Ini menunjukkan bahwa G memiliki masalah kata yang dapat dipecahkan.

Struktur aljabar dan soal kata

sunting

Ada beberapa hasil yang menghubungkan solvabilitas dari soal kata dan struktur aljabar. Yang paling signifikan dari ini adalah Teorema Boone-Higman:

Grup yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan jika dan hanya jika dapat disematkan dalam grup sederhana yang dapat disematkan dalam grup yang disajikan secara terbatas.

Dipercaya secara luas bahwa konstruksi harus mungkin dilakukan sehingga kelompok sederhana itu sendiri disajikan dengan baik. Jika demikian, orang akan sulit untuk membuktikannya karena pemetaan dari presentasi ke grup sederhana harus non-rekursif.

Berikut ini telah dibuktikan oleh Bernhard Neumann dan Angus Macintyre:

Grup yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan jika dan hanya jika dapat disematkan di setiap grup tertutup aljabar

Hal yang luar biasa tentang hal ini adalah bahwa grup tertutup secara aljabar sangat liar sehingga tidak ada yang memiliki presentasi rekursif.

Hasil tertua yang menghubungkan struktur aljabar dengan solvabilitas masalah kata adalah teorema Kuznetsov:

Grup sederhana yang disajikan secara rekursif S memiliki masalah kata yang dapat dipecahkan.

Untuk membuktikan ini mari ⟨X|R⟩ menjadi presentasi rekursif untuk S . Pilih a ∈ S sehingga a ≠ 1 pada S .

Jika w adalah kata pada generator X dari S , maka biarkan:

 

Ada fungsi rekursif   yaitu:

 

Menulis:

 

Kemudian karena konstruksi f seragam, ini adalah fungsi rekursif dari dua variabel.

Maka dari itu:   bersifat rekursif. Dengan konstruksi:

 

Karena S adalah grup sederhana, satu-satunya grup hasil bagi adalah dirinya sendiri dan grup trivial. Karena itu:

 

Adanya fungsi seperti itu cukup untuk membuktikan bahwa masalah kata dapat dipecahkan untuk S .

Bukti ini tidak membuktikan adanya algoritma yang seragam untuk menyelesaikan masalah kata untuk kelas kelompok ini. Ketidakseragaman terletak pada pemilihan elemen non-sepele dari kelompok sederhana. Tidak ada alasan untuk menganggap bahwa ada fungsi rekursif yang memetakan presentasi dari grup sederhana ke elemen non-trivial grup. Namun, dalam kasus grup yang disajikan secara terbatas, kami tahu bahwa tidak semua generator bisa sepele (Generator individual apa pun, tentu saja). Menggunakan fakta ini dimungkinkan untuk memodifikasi bukti untuk menunjukkan:

Masalah kata dapat dipecahkan secara seragam untuk kelas kelompok sederhana yang disajikan secara terbatas.

Lihat pula

sunting

Catatan

sunting
  1. ^ Dehn 1911.
  2. ^ Dehn 1912.
  3. ^ Greendlinger, Martin (June 1959), "Dehn's algorithm for the word problem", Communications on Pure and Applied Mathematics, 13 (1): 67–83, doi:10.1002/cpa.3160130108. 
  4. ^ Lyndon, Roger C. (September 1966), "On Dehn's algorithm", Mathematische Annalen, 166 (3): 208–228, doi:10.1007/BF01361168, hdl:2027.42/46211 , diarsipkan dari versi asli tanggal 2013-12-28, diakses tanggal 2020-12-11. 
  5. ^ Schupp, Paul E. (June 1968), "On Dehn's algorithm and the conjugacy problem", Mathematische Annalen, 178 (2): 119–130, doi:10.1007/BF01350654, diarsipkan dari versi asli tanggal 2016-03-05, diakses tanggal 2020-12-11. 
  6. ^ Novikov, P. S. (1955), "On the algorithmic unsolvability of the word problem in group theory", Proceedings of the Steklov Institute of Mathematics (dalam bahasa Rusia), 44: 1–143, Zbl 0068.01301 
  7. ^ Boone, William W. (1958), "The word problem" (PDF), Proceedings of the National Academy of Sciences, 44 (10): 1061–1065, doi:10.1073/pnas.44.10.1061, PMC 528693 , PMID 16590307, Zbl 0086.24701 
  8. ^ J.A. Todd and H.S.M. Coxeter. "Metode praktis untuk menghitung koset dari kelompok abstrak hingga", Proc, Edinburgh Math Soc. (2), 5, 25---34. 1936
  9. ^ D. Knuth and P. Bendix. "Simple word problems in universal algebras." Computational Problems in Abstract Algebra (Ed. J. Leech) pages 263--297, 1970.
  10. ^ Rotman 1994.
  11. ^ H.Simmons, "The word problem for absolute presentations." J. London Math. Soc. (2) 6, 275-280 1973
  12. ^ Roger C. Lyndon, Paul E Schupp, Combinatorial Group Theory, Springer, 2001
  13. ^ Collins & Zieschang 1990, hlm. 149.
  14. ^ Collins & Zieschang 1993, Cor. 7.2.6.
  15. ^ Collins 1969.
  16. ^ Borisov 1969.
  17. ^ Collins 1972.
  18. ^ Collins 1986.
  19. ^ Kami menggunakan versi yang dikoreksi dari John Pedersen's A Catalogue of Algebraic Systems

Referensi

sunting