  Solutions of the Strong CP Problem based on the spontaneous breaking of CP
must feature a non-generic structure and simultaneously explain a coincidence
between a priori unrelated CP-even and CP-odd mass scales. We show that these
properties can emerge from gauge invariance and a CP-conserving, but otherwise
generic, physics at the Planck scale. In our scenarios no fundamental scalar is
introduced beyond the Standard Model Higgs doublet, and CP is broken at
naturally small scales by a confining non-abelian dynamics. This approach is
remarkably predictive: robustness against uncontrollable UV corrections to the
QCD topological angle requires one or more families of vector-like quarks below
a few $10$'s of TeV, hence potentially accessible at colliders. Because CP
violation is communicated to the SM at these super-soft scales, our solution of
the Strong CP Problem is not spoiled by the presence of heavy new states
motivated by other puzzles in physics beyond the Standard Model. In addition,
these models generically predict a dark sector that may lead to interesting
cosmological signatures.
