  Thanks to earlier work of Koiran, it is known that the truth of the
Generalized Riemann Hypothesis (GRH) implies that the dimension of algebraic
sets over the complex numbers can be determined within the
polynomial-hierarchy. The truth of GRH thus provides a direct connection
between a concrete algebraic geometry problem and the P vs.NP Problem, in a
radically different direction from the geometric complexity theory approach to
VP vs. VNP. We explore more plausible hypotheses yielding the same speed-up.
One minimalist hypothesis we derive involves improving the error term (as a
function of the degree, coefficient height, and $x$) on the fraction of primes
$p\!\leq\!x$ for which a univariate polynomial has roots mod $p$. A second
minimalist hypothesis involves sharpening current zero-free regions for
Dedekind zeta functions. Both our hypotheses allow failures of GRH but still
enable complex dimension computation in the polynomial hierarchy.
