  We assess the detectability of a nanohertz gravitational wave (GW) background
with respect to additive red and white noise in the timing of millisecond
pulsars. We develop detection criteria based on the cross-correlation function
summed over pulsar pairs in a pulsar timing array. The distribution of
correlation amplitudes is found to be non-Gaussian and highly skewed, which
significantly influences detection and false-alarm probabilities. When only
white noise and GWs contribute, our detection results are consistent with those
found by others. Red noise, however, drastically alters the results. We discuss
methods to meet the challenge of GW detection ("climbing mount significance")
by distinguishing between GW-dominated and red or white-noise limited regimes.
We characterize detection regimes by evaluating the number of millisecond
pulsars that must be monitored in a high-cadence, 5-year timing program for a
GW background spectrum $h_c(f) = A f^{-2/3}$ with $A = 10^{-15}$ yr$^{-2/3}$.
Unless a sample of 20 super-stable millisecond pulsars can be found --- those
with timing residuals from red-noise contributions $\sigma_r \lesssim 20$ ns
--- a much larger timing program on $\gtrsim 50 - 100$ MSPs will be needed. For
other values of $A$, the constraint is $\sigma_r \lesssim 20 {\rm ns}
(A/10^{-15} {\rm yr}^{-2/3})$. Identification of suitable MSPs itself requires
an aggressive survey campaign followed by characterization of the level of spin
noise in the timing residuals of each object. The search and timing programs
will likely require substantial fractions of time on new array telescopes in
the southern hemisphere as well as on existing ones.
