Timeline for Complexity of computing the minimum degree of a faithful linear representation of a finite group
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2012 at 2:48 | comment | added | Alex B. | The permutation representation case has been discussed before: mathoverflow.net/questions/48928/… | |
| Jan 18, 2012 at 23:21 | comment | added | Benjamin Steinberg | @Derek, I would naively guess finding the minimal degree faithful permutation degree even more difficult. I conjecture for finite semigroups the minimum degree faithful linear representation is NP-hard to compute but one would guess the group case should be easier. | |
| Jan 18, 2012 at 21:01 | comment | added | Derek Holt | The problem of finding the minimal degree faithful permutation representation of a finite group presents similar difficulties. For practical purposes, you might be content with a reasonably low degree solution, but it can be hard to prove that your solution is actually minimal. What would be interesting would be to find (families of) examples in which your problem seemed to be hard. | |
| Jan 18, 2012 at 14:21 | comment | added | Benjamin Steinberg | @Mariano, thanks for the comments. I assumed getting the character table was fast since GAP does it well but still I have no idea how quickly one can find the cover. For abelian groups one can trivially find the minimum faithful degree, it is the minimal number of generators which has been discussed on MO before. In general the number of conjugacy classes can be 1/4 the size of the group, although usually it is smaller. | |
| Jan 18, 2012 at 7:38 | comment | added | Mariano Suárez-Álvarez | Are there useful bounds for the quotient (minimum faithful degree)/$|G|$? | |
| Jan 18, 2012 at 7:29 | comment | added | Mariano Suárez-Álvarez | (Once you have the character table you need to solve an instance of the minimal set cover problem, though, which is NP-hard; the size of the input is the number of conjugacy classes, which is much smaller than the size of the group, so this might not be enough to ruin the P-ness of the computating of the table) | |
| Jan 18, 2012 at 7:12 | comment | added | Mariano Suárez-Álvarez | You can find the character table in polynomial time, according to mathoverflow.net/questions/45560/… | |
| Jan 18, 2012 at 4:54 | history | asked | Benjamin Steinberg | CC BY-SA 3.0 |