2
$\begingroup$

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?

  • 3
    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 (http://en.wikipedia.org/wiki/Real_closed_field#Model_Theory:_decidability_and_quantifier_elimination) and I think known even earlier over the complex numbers (a modern approach is through Grobner bases: http://en.wikipedia.org/wiki/Gr%C3%B6bner_basis), but you should specify what "complexity" means in this context.2012-02-07
  • 2
    For a survey of what was known as of 2003, see Poonen's _Hilbert's tenth problem over rings of number-theoretic interest_ (http://math.mit.edu/~poonen/papers/aws2003.pdf).2012-02-07
  • 1
    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_ (http://math.mit.edu/~poonen/papers/millennial.pdf).2012-02-07
  • 0
    @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.2012-02-07
  • 0
    Actually, I'm confused: by the Hilbert Nullstellensatz, if, over the complex numbers, we don't have a solution to the equations, then we must have a witness for this, i.e., a set of $ m $ polynomials $ g_1,\ldots,g_m $, such that $ g_1 f_1 + \ldots + g_m f_m=1$. So this can't be undecidable.2012-02-07
  • 1
    Over the rationals, it's not known to be decidable. Over the complex numbers, it's classically known to be decidable by elimination theory (http://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.2012-02-07
  • 0
    Ok, you might be right. If one is interested in the complement of this problem: that is, decide whether it is unsolvable, then a direct consequence of Hilbert's Nullstellensatz yields that over $ \mathbb C$, the problem is r.e. I don't know if this gives decidability, indeed. Now the question is this: do you know what is the complexity of this problem over the complex numbers? Which model was actually considered?2012-02-07
  • 0
    You can assume that the coefficients are rationals to avoid dealing with real number inputs (which I think is the usual way to define the problem).2012-02-09
  • 0
    @Kaveh, why can you assume that? My question is indeed about different fields. Also, over the rationals, what is the complexity of the problem? Qiaochu says it's open whether it is decidable (over Q).2012-02-11
  • 0
    @Dilworth, the important thing is the field that contains the solutions not the field that coefficients are coming from. That is the classical setting where the problem is studied.2012-02-13
  • 0
    @Kaveh, sorry, but I don't really follow. If the polynomials have real coefficients for example, so why can I assume the field is $\mathbb Q $? Also, if the initial polynomials have only rational coefficients, is it the case that their solution should be rational as well? Also, why would the rational case be the only setting where the problem is studied?2012-02-13
  • 0
    @Dilworth, I didn't say you can assume that. What I am saying is the classical problem is when the coefficients are from the countable Q. The problem can be studied when the coefficients are from an uncountable field like R but then the problem is not classical computability problem and is not comparable to the classical Diophantine problem. It is also not (classical) complexity theory, P and NP are for classical problems where inputs are finite objects.2012-02-13
  • 0
    @Dilworth, If that is what you want (i.e. coefficients from an uncountable field) then you have to specify what model of computation you are going to use, the answer will depend on that. See [this](http://cstheory.stackexchange.com/questions/2119/the-reasons-for-bss-real-ram-model-being-prefered-in-computational-geometry) to get an idea of why you need to specify the model for computation over reals.2012-02-13

0 Answers 0