Timeline for The complexity of the word problem in linear groups
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2011 at 5:47 | comment | added | user6976 | @Ben: Yes, they prove the same (and more) in the case of prime characteristic. | |
| Nov 10, 2011 at 4:32 | comment | added | Benjamin Steinberg | @Mark, I think Simon's paper fields f ther characteristic are also considered. | |
| Nov 10, 2011 at 4:09 | comment | added | user6976 | Also in our survey with Olga Kharlampovich, it is written that the word problem in every matrix group is decidable in polynomial time. But I forgot why we wrote that and there is no reference there. | |
| Nov 10, 2011 at 4:03 | comment | added | user6976 | In math.stevens.edu/~rgilman/ccny/other.pdf Bob Gilman gives two more references. | |
| Nov 10, 2011 at 3:34 | comment | added | Benjamin Steinberg | The above comment is more relevant to your previous question since the proof uses the randomized polytime algorithm to check if a polynomial is 0. | |
| Nov 10, 2011 at 2:39 | comment | added | Benjamin Steinberg | According to Markus Lohrey, the compressed word problem for linear groups is in coRP. That means there is a polynomial time probabilistic Turing machine which says No if the element is not the identity and gets Yes correct at least half the time. It is believed coRP is smaller than NP so even the compressed word problem is good. | |
| Nov 10, 2011 at 2:30 | vote | accept | CommunityBot | moved from User.Id=6976 by developer User.Id=69903 | |
| Nov 10, 2011 at 2:30 | history | edited | Benjamin Steinberg | CC BY-SA 3.0 |
Added reference
|
| Nov 10, 2011 at 2:21 | comment | added | Benjamin Steinberg | Here is a link dl.acm.org/… | |
| Nov 10, 2011 at 2:16 | history | answered | Benjamin Steinberg | CC BY-SA 3.0 |