Can one quickly test whether an element is in a set by asking whether a different element is in the set? Can sets be split into two parts, each of which is many-one polynomial-time equivalent to each other and to the original set? These issues, polynomial-time many-one autoreducibility and polynomial-time many-one mitoticity, naturally will have varying answers depending on the set. However, this paper shows that every complete set for a broad range of important complexity classes, including nondeterministic polynomial-time (NP), is polynomial-time many-one autoreducible. The paper establishes many other results, including showing that all complete sets for deterministic exponential time are polynomial-time many-one mitotic. These results resolve long-open issues and deepen the understanding of the structure of complete sets.