Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 (…) and I think known even earlier over the complex numbers (a modern approach is through Grobner bases:, 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 ( – 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 ( – 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 ( 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.