Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: NP-completeness in the gossip monoid   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.

36
The categories of this paper are: cmp-lg
3
The categories of this paper are: physics
17
The categories of this paper are: q-fin
21
The categories of this paper are: adap-org
16
The categories of this paper are: stat
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg
15
The categories of this paper are: nucl-ex
11
The categories of this paper are: hep-lat
7
The categories of this paper are: hep-th
1
The categories of this paper are: cs
26
The categories of this paper are: bayes-an
12
The categories of this paper are: nucl-th
35
The categories of this paper are: mtrl-th
18
The categories of this paper are: econ
14
The categories of this paper are: math-ph