  Population protocols [Angluin et al., PODC, 2004] are a model of distributed
computation in which indistinguishable, finite-state agents interact in pairs
to decide if their initial configuration, i.e., the initial number of agents in
each state, satisfies a given property. In a seminal paper Angluin et al.
classified population protocols according to their communication mechanism, and
conducted an exhaustive study of the expressive power of each class, that is,
of the properties they can decide [Angluin et al., Distributed Computing,
2007]. In this paper we study the correctness problem for population protocols,
i.e., whether a given protocol decides a given property. A previous paper
[Esparza et al., Acta Informatica, 2017] has shown that the problem is
decidable for the main population protocol model, but at least as hard as the
reachability problem for Petri nets, which has recently been proved to have
non-elementary complexity. Motivated by this result, we study the computational
complexity of the correctness problem for all other classes introduced by
Angluin et al., some of which are less powerful than the main model. Our main
results show that for the class of observation models the complexity of the
problem is much lower, ranging from ${\Pi}_2^p$ to PSPACE.
