Jelaskan Kompleksitas grup dari Teori Krohn–Rhodes

Kompleksitas Krohn–Rhodes (juga disebut kompleksitas grup atau hanya kompleksitas) dari semigroup terbatas  S  adalah jumlah grup paling sedikit dalam produk karangan bunga dari grup hingga dan semigrup aperiodik hingga.

Semua semigroup aperiodik hingga memiliki kompleksitas 0, sedangkan grup berhingga non- trivial memiliki kompleksitas 1. Faktanya, ada setengah grup dari setiap kompleksitas bilangan bulat non-negatif. Misalnya, untuk sembarang  n  yang lebih besar dari 1, semigroup perkalian dari semua (n+1)×(n+1) segitiga atas matriks di atas setiap terbatas terbatas bidang memiliki kompleksitas  n  (Kambites, 2007).

Masalah terbuka utama dalam teori semigroup hingga adalah  desidabilitas kompleksitas : apakah ada algoritme yang akan menghitung kompleksitas Krohn–Rhodes dari semigrup hingga, diberi tabel perkalian?

Batas atas dan batas bawah yang lebih tepat pada kompleksitas telah diperoleh (lihat, misalnya Rhodes & Steinberg, 2009). Rhodes telah menduga bahwa masalahnya sudah pasti.