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?

  • 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