Nontrivial criteria for polynomials to have no common zeros?

When we work in $C[x_1,x_2,...,x_n]$,here $C$ denotes the complex field, we know that when polynomials $f_1,f_2,...,f_k$ have no common zeros, then there exists polynomials $g_1,...,g_k$ , such that the sum of $g_i\cdot f_i$ is $1$, (Nullstellensatz). However, this theorem doesn't seem to have any practical value, consider the following problem:

Is there any nontrivial criterion such that we can determine whether some polynomials (chosen randomly) have common zeros or not by using it? Of course, I don't want to use the Grobner base theory, what I need is just a criterion involving information on the algebraic properties of the given polynomials, something just like Eisensten's criterion on irreducibility.

• The plural of criterion is criteria. Dec 11, 2010 at 7:54
• Yes - minor editing carried out. Dec 11, 2010 at 8:53
• @ougao, well naively speaking, if you consider the chance of a (random) polynomial $f(x)$ sharing a (particular) zero with (another random) polynomial $g(y)$ as being "equally likely" as the chance that these two (random) polynomials do not share any zeroes, then a "trivial" criterion (at least for me) would be: $h(0) = \frac{1}{2}$ where $h(z) = ABS(f(x) - g(y))$. I hope that trivial observation will get to help you with your problem somehow. Dec 11, 2010 at 9:17
• I don't understand the statement "this theorem doesn't seem to have any practical value". There is an algorithm (the resultant algorithm, as pointed out by Myerson), which has many efficientimplementations and which is used in every known computer algebra system. As for the complexity issues, note that a general polynomial of degree $d$ in $n$ variables has a LOT of terms, so questions about such polynomials are sure to be very hard. If you restrict to SPARSE polynomials, the question becomes interesting. This is covered in the book by R. Zippel (Efficient Polynomial Computation). Dec 11, 2010 at 16:08
• OK, so it seems the question really is, how can I construct nontrivial examples of polynomials with no common zeros. That of course depends on what "nontrivial" means. Maybe this is trivial: let $f_1,\dots,f_{k-1}$ and $g_1,\dots,g_{k-1}$ be arbitrary, and let $f_k=f_1g_1+\cdots+f_{k-1}g_{k-1}+1$; then $f_1,\dots,f_k$ have no common zeros. Dec 11, 2010 at 21:38

Not known. Your problem is $NP_\mathbf{C}$-complete in the Blum-Shub-Smale complexity model. So anything significantly simpler than Groebner basis would yield significant progress on the $P=NP$ question over $\mathbf{C}$ compared to the current state of the art.
• Hmm. I thought this was what the resultant was for. Certainly works for $n=1$, $k=2$, and there is such a thing as the resultant in more general cases. Dec 11, 2010 at 5:19
• Sorry for my ambiguous words, I just want to say that when I write down some polynomials, I want to detect whether they have no common zeros, if not, then maybe I can go to search the coefficients $g_i$,or at least say something on them. Dec 11, 2010 at 17:33