2016/06/03 by Fenner, Peter, Johnson, Marianne, Kambites, Mark
#20M05 #20M20 #68Q17 #Combinatorics (math.CO) #FOS: Mathematics #Rings and Algebras (math.RA)
paper · doi:10.48550/arxiv.1606.01026
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.