Timeline for Decision problems for which it is unknown whether they are decidable
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Dec 3, 2019 at 11:29 | history | made wiki | Post Made Community Wiki by Todd Trimble | ||
| Nov 10, 2019 at 10:39 | comment | added | Carl-Fredrik Nyberg Brodda | @AsafKaragila Another decision problem which remains open is the conjugacy problem for torsion-free one-relator groups. The conjugacy problem is the problem of deciding whether two given elements are conjugate or not -- it is clearly at least as hard as the word problem. It was solved in 1968 for one-relator groups with torsion by... | |
| Nov 9, 2019 at 22:57 | history | edited | Carl-Fredrik Nyberg Brodda | CC BY-SA 4.0 |
The canonical homomorphism is from the free group on A, not A*.
|
| Nov 9, 2019 at 14:32 | comment | added | Asaf Karagila♦ | Wow, you wrote this entire answer without mentioning B. B. Newman! Amazing! | |
| Nov 9, 2019 at 7:25 | comment | added | Dominic van der Zypen | Thanks Carl-Fredrik! | |
| Nov 9, 2019 at 7:23 | comment | added | Carl-Fredrik Nyberg Brodda | @DominicvanderZypen The word problem goes back to Dehn in the early 1910s, but Adjan in the 1960s looked a great deal at one-relation semigroups in particular, reducing it to a number of cases (and also solving the word problem for one-relator semigroups $\langle A \mid u = 1 \rangle$). | |
| Nov 9, 2019 at 7:13 | comment | added | Dominic van der Zypen | amazing - do you happen to know who formulated that problem first? | |
| Nov 8, 2019 at 19:39 | comment | added | Carl-Fredrik Nyberg Brodda | @DominicvanderZypen Thank you -- it is indeed surprising. A closely related problem you may be interested in is the fact that the word problem for one-relation semigroups $\langle A \mid u = v \rangle$ remains a long-standing open problem. | |
| Nov 8, 2019 at 14:00 | comment | added | Dominic van der Zypen | That's a really nice answer, and surprising, thanks Carl-Fredrik! | |
| Nov 8, 2019 at 10:37 | history | answered | Carl-Fredrik Nyberg Brodda | CC BY-SA 4.0 |