Timeline for Groups where word problem is solvable, but not quickly?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2016 at 17:47 | answer | added | YCor | timeline score: 5 | |
| Dec 29, 2016 at 5:31 | answer | added | Izaak Meckler | timeline score: 2 | |
| Aug 11, 2015 at 13:48 | vote | accept | Andrew Penland | ||
| Aug 9, 2015 at 15:42 | answer | added | Igor Rivin | timeline score: 3 | |
| Aug 9, 2015 at 11:22 | answer | added | Andreas Thom | timeline score: 20 | |
| Aug 9, 2015 at 6:08 | comment | added | HJRW | There are fairly standard constructions that should build fg groups for whom the word problem is equivalent to the membership problem for your favourite subset $S\subseteq \mathbb{N}$. For instance, I think the word problem in $\langle a,b\mid [a^{-n}ba^n,b]=1\Leftrightarrow n\in S\rangle$ can be seen to be at least as difficult as membership of $S$. (Of course, one needs to check that the word problem is actually solvable, but I don't think that's too difficult in this case.) For finitely presented examples, one could invoke Clapham's improvement of Higman's embedding theorem. | |
| Aug 9, 2015 at 4:35 | review | First posts | |||
| Aug 9, 2015 at 5:47 | |||||
| Aug 9, 2015 at 4:32 | history | asked | Andrew Penland | CC BY-SA 3.0 |