  We introduce a natural-valued complexity c(X) for pairs X=(M,L), where M is a
closed orientable 3-manifold and L is a link contained in M. The definition
employs simple spines, but for well-behaved X's we show that c(X) equals the
minimal number of tetrahedra in a triangulation of M containing L in its
1-skeleton. Slightly adapting Matveev's recent theory of roots for graphs, we
carefully analyze the behaviour of c under connected sum away from and along
the link. We show in particular that c is almost always additive, describing in
detail the circumstances under which it is not. To do so we introduce a certain
(0,2)-root for a pair X, we show that it is well-defined, and we prove that X
has the same complexity as its (0,2)-root. We then consider, for links in the
3-sphere, the relations of c with the crossing number and with the hyperbolic
volume of the exterior, establishing various upper and lower bounds. We also
specialize our analysis to certain infinite families of links, providing rather
accurate asymptotic estimates.
