Commutativity.hpp File Reference

Plans regarding notions associated to commutativity in general. More...

Go to the source code of this file.

Detailed Description

Plans regarding notions associated to commutativity in general.

Complexity of finding centralising elements
  • We have already centraliser_grd, bicentraliser_grd and centre.
  • Given an implicit representation of a groupoid together with the guarantee that "short" representations always exists (a "black-box" groupoid), the problem of finding a centraliser of a subset is in NP.
  • Is it NP-complete?
  • In a monoid the problem of finding just one centralising element needs to exclude the neutral element, and for centralising just a single element we also need to exclude the subgroupoid generated by this single element. So perhaps the general problem is, given some subgroupoid, finding a centralising element not in this subgroupoid.
  • Does there exist at this level of generality any other algorithm for finding centralising elements (one/all) other running through all elements?
  • Also the task of sampling needs consideration.
  • DONE Likely these functions should be renamed "centraliser_grd", "bicentraliser_grd" and "centre".

Definition in file Commutativity.hpp.