# Complexity of finding solutions for a system of polynomial equations

Problem A: Given a set of polynomial equations $f_1=0,\ldots,f_m=0$, where the $f_i$'s are multivariate polynomials with $n$ variables over a field $\mathbb F$, decide whether there is a (simultaneous) solution to these equations.

Question: What is the computational complexity of Problem A?

Note: Over finite fields $\mathbb F$, Problem A seems to be NP-complete. But what about over the reals, rationals, complex numbers?

-
What does "computational complexity" mean over the real or complex numbers? Over the rational numbers, it's open whether this problem is even decidable (as far as I know, anyway). It's known to be decidable over the reals by a result of Tarski (en.wikipedia.org/wiki/…) and I think known even earlier over the complex numbers (a modern approach is through Grobner bases: en.wikipedia.org/wiki/Gr%C3%B6bner_basis), but you should specify what "complexity" means in this context. –  Qiaochu Yuan Feb 7 '12 at 17:45
For a survey of what was known as of 2003, see Poonen's Hilbert's tenth problem over rings of number-theoretic interest (math.mit.edu/~poonen/papers/aws2003.pdf). –  Qiaochu Yuan Feb 7 '12 at 17:48
In fact, strictly speaking (as far as I know, again) it's strongly suspected, but not proven, that this problem is decidable over $\mathbb{Q}$ even for the very special case that the $f_i$ define a curve of genus $1$. Essentially the only cases over $\mathbb{Q}$ that are known to be decidable are when the $f_i$ define a finite set of points together with a finite union of curves of genus $0$. See Poonen, again, Rational points on curves (math.mit.edu/~poonen/papers/millennial.pdf). –  Qiaochu Yuan Feb 7 '12 at 17:55
@Yuan, I don't know exactly---that is my questions: over the reals/complex, maybe one can use the Blum-Shub-Smale model? Over the rationals--I didn't know it's undecidable, thanks. –  Dilworth Feb 7 '12 at 18:11
Over the rationals, it's not known to be decidable. Over the complex numbers, it's classically known to be decidable by elimination theory (en.wikipedia.org/wiki/Elimination_theory) although, as I said, I think a more modern approach would go through Grobner bases. I'm not sure what you mean by your comment about the Nullstellensatz. –  Qiaochu Yuan Feb 7 '12 at 18:20