  The classes PPA-$p$ have attracted attention lately, because they are the
main candidates for capturing the complexity of Necklace Splitting with $p$
thieves, for prime $p$. However, these classes were not known to have complete
problems of a topological nature, which impedes any progress towards settling
the complexity of the Necklace Splitting problem. On the contrary, topological
problems have been pivotal in obtaining completeness results for PPAD and PPA,
such as the PPAD-completeness of finding a Nash equilibrium [Daskalakis et al.,
2009, Chen et al., 2009b] and the PPA-completeness of Necklace Splitting with 2
thieves [Filos-Ratsikas and Goldberg, 2019].
  In this paper, we provide the first topological characterization of the
classes PPA-$p$. First, we show that the computational problem associated with
a simple generalization of Tucker's Lemma, termed $p$-polygon-Tucker, as well
as the associated Borsuk-Ulam-type theorem, $p$-polygon-Borsuk-Ulam, are
PPA-$p$-complete. Then, we show that the computational version of the
well-known BSS Theorem [Barany et al., 1981], as well as the associated
BSS-Tucker problem are PPA-$p$-complete. Finally, using a different
generalization of Tucker's Lemma (termed $\mathbb{Z}_p$-star-Tucker), which we
prove to be PPA-$p$-complete, we prove that $p$-thief Necklace Splitting is in
PPA-$p$. This latter result gives a new combinatorial proof for the Necklace
Splitting theorem, the only proof of this nature other than that of Meunier
[2014].
  All of our containment results are obtained through a new combinatorial proof
for $\mathbb{Z}_p$-versions of Tucker's lemma that is a natural generalization
of the standard combinatorial proof of Tucker's lemma by Freund and Todd
[1981]. We believe that this new proof technique is of independent interest.
