  We suggest here that CP is a discrete {\it gauge} symmetry, and is therefore
not violated by quantum gravity. We show that four dimensional CP can arise as
a discrete gauge symmetry in theories with dimensional compactification, if the
original number of Minkowski dimensions equals $8k+1$, $8k+2$ or $8k+3$, and if
there are certain restrictions on the gauge group; these conditions are met by
superstrings. CP may then be broken spontaneously below $10^9$ GeV, explaining
the observed CP violation in the kaon system without inducing a large EDMN. We
discuss the phenomenology of such models, as well as the peculiar nature of
cosmic ``CP strings'' which could be produced at the compactification scale.
Such strings have the curious property that a particle carried around the
string is turned into its CP conjugate. A single CP string renders four
dimensional spacetime nonorientable.
