(Miguel's post follows) On 2 October 2015 at 14:50, <mma...@unizar.es> wrote: > What you say is pretty much correct, but something must be added. > > Solving the word problem (that is, testing equality) is not only very hard: it > is an undecidable problem in general. That is: there can't be any algorithm > that determines if two words correspond to the same element of an arbitrary > finitely presented group. So "implementing a decent __eq__" is an impossible > task. > > There is some hope though. It is impossible to solve the problem in general, > but there are some techniques that can be succesful in many cases (and i guess > most of the cases you would be interested in fall in this lucky category). > > As you said, computing a normal form is a harder problem than testing > equality... but most of the techniques that can be used to attack the word > problem happen to be based on some kind of normal form. So, even if in theory > the normal form problem is harder than the word problem, in practice almost > always the solution for both problems come together: either we are able to > compute a normal form, or we are unable to decide equality. > > The case of cyclic groups that you mention is a very easy one. They are > finite, > abelian and have a very simple confluent rewriting system. Every possible > techinque to solve the word problem works immediately. That is why, if you > delegate the equality to gap (which is what happen when the hash does not > distinguish), it is able to determine if two elements are the same or not. > > But as I said, that is incidental. It happens because we are dealing with very > simple presentations, and the basic reductions that gap does internally are > enough to distinguish the elements. If, for instance, we would present the > same groups with a more complicated presentation, it could happen that those > simple reductions wouldn't be enough to correctly distinguish the elements. > > In general, it is not a good idea to use the structure of a finitely presented > group if you need to accurately distinguish elements. If that is your case, > and you group allows any other way to be represented (PermutationGroup, > AbelianGroup, MatrixGroup...), it is a much better idea to do so: in those > structures equality testing is trivial (in fact you have a unique canonical > form of each element), whereas in the finitely presented group theory it is > undecidable. > > I hope i clarified things a bit. > > Best, > > Miguel
-- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
