We show completeness results for secret sharing schemes realizing mNP access structures. We begin by proposing a new, Euclidean-type, division technique for access structures. Using this new technique we obtain several results in characterizing access structures for efficient (unconditionally secure) secret sharing schemes: – We show a useful transformation that achieves efficient schemes for complex access structures using schemes realizing simple access structures. – We show that, assuming every access structure in P ∩ mono admits efficient secret sharing, the existence of an efficient secret sharing for an access structure in mNP that is also complete for mNP under Karp/Levin monotone-reductions implies secret sharing schemes for all of mNP. – We finally improve upon the above completeness result by obtaining the same under ordinary Karp/Levin reductions.