On the efficiency of effective Nullstellensätze
Let k be an infinite and perfect field, x1, ..., xn indeterminates over k and let f1, ..., fs be polynomials in k[x1, ..., xn] of degree bounded by a given number d, which satisfies d≥n. We prove an effective affine Nullstellensatz of the following particular form: For arbitrary given parameters d,...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p56_Giusti |
| Aporte de: |
| Sumario: | Let k be an infinite and perfect field, x1, ..., xn indeterminates over k and let f1, ..., fs be polynomials in k[x1, ..., xn] of degree bounded by a given number d, which satisfies d≥n. We prove an effective affine Nullstellensatz of the following particular form: For arbitrary given parameters d, s, n there exists a probabilistic (randomized) arithmetic network over k of size sO(1)dO(n) and depth O(n4log2sd) solving the following task: It decides whether the ideal generated by f1, ..., fs in k[x1, ..., xn] is trivial and, if this is the case, it produces a straight-line program of size sO(1)dO(n) and depth O(n4log2sd) in the function field k(x1, ..., xn) which computes polynomials p1, ..., ps of k[x1, ..., xn] of degree {Mathematical expression} satisfying {Mathematical expression} © 1993 Birkhäuser Verlag. |
|---|