Before revision:  Finally, using a different generalization of Tucker's Lemma (termed Z_p-star-Tucker), which we prove to be PPA-p-complete, we prove that p-thieves Necklace Splitting is in PPA-p   . All of our containment results are obtained through a new combinatorial proof for 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].
After revision:  Finally, using a different generalization of Tucker's Lemma (termed Z_p-star-Tucker), which we prove to be PPA-p-complete, we prove that p-thieves 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 . All of our containment results are obtained through a new combinatorial proof for 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].