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,...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Giusti, M., Heintz, J., Sabia, J.
Formato: JOUR
Materias:
Complexity
computer algebra
effective Nullstellensatz
elimination theory
straight-line program
Subject classification: 68C25
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p56_Giusti
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_10163328_v3_n1_p56_Giusti
record_format dspace
spelling todo:paper_10163328_v3_n1_p56_Giusti2023-10-03T15:56:22Z On the efficiency of effective Nullstellensätze Giusti, M. Heintz, J. Sabia, J. Complexity computer algebra effective Nullstellensatz elimination theory straight-line program Subject classification: 68C25 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. Fil:Sabia, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p56_Giusti
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Complexity
computer algebra
effective Nullstellensatz
elimination theory
straight-line program
Subject classification: 68C25
spellingShingle Complexity
computer algebra
effective Nullstellensatz
elimination theory
straight-line program
Subject classification: 68C25
Giusti, M.
Heintz, J.
Sabia, J.
On the efficiency of effective Nullstellensätze
topic_facet Complexity
computer algebra
effective Nullstellensatz
elimination theory
straight-line program
Subject classification: 68C25
description 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.
format JOUR
author Giusti, M.
Heintz, J.
Sabia, J.
author_facet Giusti, M.
Heintz, J.
Sabia, J.
author_sort Giusti, M.
title On the efficiency of effective Nullstellensätze
title_short On the efficiency of effective Nullstellensätze
title_full On the efficiency of effective Nullstellensätze
title_fullStr On the efficiency of effective Nullstellensätze
title_full_unstemmed On the efficiency of effective Nullstellensätze
title_sort on the efficiency of effective nullstellensätze
url http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p56_Giusti
work_keys_str_mv AT giustim ontheefficiencyofeffectivenullstellensatze
AT heintzj ontheefficiencyofeffectivenullstellensatze
AT sabiaj ontheefficiencyofeffectivenullstellensatze
_version_ 1807314784211697664

Ejemplares similares