Mathematics – Number Theory
Scientific paper
2003-01-11
Mathematics
Number Theory
16 pages, no figures. Paper corresponds to a semi-plenary talk at FoCM 2002. This version corrects some minor typos and adds a
Scientific paper
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.
No associations
LandOfFree
Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-583921