text: Let HN denote the problem of determining whether a system of multivariate polynomials with integer coefficients has a complex root. It has long been known that HN in P implies P=NP and, thanks to recent work of Koiran, it is now known that the truth of the Generalized Riemann Hypothesis (GRH) yields the implication that HN not in NP implies P is not equal to NP. We show that the assumption of GRH in the latter implication can be replaced by either of two more plausible hypotheses from analytic number theory. The first is an effective short interval Prime Ideal Theorem with explicit dependence on the underlying field, while the second can be interpreted as a quantitative statement on the higher moments of the zeroes of Dedekind zeta functions. In particular, both assumptions can still hold even if GRH is false. We thus obtain a new application of Dedekind zero estimates to computational algebraic geometry. Along the way, we also apply recent explicit algebraic and analytic estimates, some due to Silberman and Sombra, which may be of independent interest.
  @cite_7: The parallel arithmetic complexities of matrix inversion, solving systems of linear equations, computing determinants and computing the characteristic polynomial of a matrix are shown to have the same growth rate. Algorithms are given that compute these problems in @math steps using a number of processors polynomial in n. (n is the order of the matrix of the problem.)
summary: This result immediately implies that @math can be solved by solving a linear system with @math variables and equations over the rationals (with total bit-size @math ), thus easily yielding @math . That @math then follows immediately from the fact that linear algebra can be efficiently parallelized @cite_7 .