Timeline for What is the complexity / name of word search problem in linear groups?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 11 at 18:49 | comment | added | Fiktor | @BenjaminSteinberg Yes, if you stream out the answer you can do it in $L \left\lceil\log_2(\left|S\right|)\right\rceil + O(\log(\left|S\right| L)) + \Delta$ space, where $\Delta$ is the space for checking a single word: just go over all $(\left|S\right|^{L+1} - 1)/(\left|S\right|-1)$ possible words in depth first search order, checking that the suffices are non-trivial when you do so (if suffix evaluates to 1, abandon the branch), and check the represenative is canonical before outputting words which evaluate to 1. | |
| Feb 11 at 18:11 | comment | added | Fiktor | Whether the number of such simple cycles is exponential depends on $S$: e.g. if group $G$ generated by $S$ is finite, then the number of simple cycles is finite. If $G$ is free with half of the $S$ (picking one element from every pair $\{s,s^{-1}\}$) as generators, then the number of simple cycles is also finite (they are all of the form $ss^{-1}=1$). So there are examples where $m_L$ does not grow exponentially with $L$. Even if $m_L$ grows exponentially, it can be much slower than $(\left|S\right|-1)^{L/2}$, so the complexity question is still non-trivial in that case. | |
| Feb 11 at 17:05 | comment | added | Carl-Fredrik Nyberg Brodda | @SamNead Note: $d \geq 4$ indeed $\operatorname{SL}_d(\mathbf{Z})$ is indeed not coherent (by embedding Mikhailova’s group $F_2 \times F_2$ by doubling the Sanov matrices). For $d=2$ it is obviously coherent, and for $d=3$ we don’t know. So as HJRW suggests there’s really no chance to do it even for quite small $d$. | |
| Feb 11 at 13:28 | comment | added | HJRW | @SamNead: it’s worse than that. Even if I promise you that a matrix group $G$ is finitely presented, then there is no algorithm that computes a presentation for $G$. (At least, not one that is uniform in the rank $n$.) | |
| Feb 11 at 12:54 | comment | added | Benjamin Steinberg | I would guess this can be done in polynomial space since the word problem is logspace but you are doing exponentially many words. | |
| Feb 11 at 10:16 | comment | added | Sam Nead | One possible (very weak) "description" might be "give a finite presentation" for the group generated by $S$. However, a quick google search suggests that $\mathrm{SL}(d, \mathbb{Z})$ is not coherent, so this does not work... I think? | |
| Feb 11 at 10:13 | comment | added | Sam Nead | If you want to actually build the ball of radius $R$, then the output will typically be exponential in $R$. So the running time can't be faster than that (and it probably will be about that, up to changing the base of the exponential a bit). If you want a "description of the ball of radius $R$" then you need to say what you mean by "description". | |
| Feb 11 at 8:40 | comment | added | Fiktor | @HJRW Thank you! Yes, the word problem is a decision problem, and I'm interested in a related search problem. Yes, effectively I'm looking for a problem of computing a description of the ball of radius $L/2$ in the Cayley graph (specifically, description in terms of simple cycles passing through the origin). | |
| Feb 11 at 6:51 | comment | added | HJRW | Perhaps this keyword is useful: you are asking about the word problem in the group $G$ generated by $S$. This is usually phrased as determining if a single word represents a non-trivial element, but you are asking how long it will take to construct the entire ball of radius $L/2$ in the Cayley graph. | |
| Feb 11 at 5:41 | history | asked | Fiktor | CC BY-SA 4.0 |