  Gossip monoids form an algebraic model of networks with exclusive, transient
connections in which nodes, when they form a connection, exchange all known
information. They also arise naturally in pure mathematics, as the monoids
generated by the set of all equivalence relations on a given finite set under
relational composition. We prove that a number of important decision problems
for these monoids (including the membership problem, and hence the problem of
deciding whether a given state of knowledge can arise in a network of the kind
under consideration) are NP-complete. As well as being of interest in their own
right, these results shed light on the apparent difficulty of establishing the
cardinalities of the gossip monoids: a problem which has attracted some
attention in the last few years.
