|
Zapiski Nauchnykh Seminarov POMI, 2001, Volume 277, Pages 47–52
(Mi znsl1428)
|
|
|
|
Double-exponential growth of the number of vectors of solutions of polynomial systems
D. Yu. Grigor'evab a St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
b University of Rennes 1
Abstract:
In [4] it was proved an upper bound $d^{O\left(\left(\smallmatrix n+d\\n\endsmallmatrix\right)\right)}$ on the number of vectors of multiplicities of the solutions of systems of the form $g_1=\ldots=g_n=0$ (provided, it has a finite number of solutions) of polynomials $g_1,\dots,g_n\in F[X_1,\dots,X_n]$ with degrees $\deg g_i\le d$ (the field $F$ is algebraically closed). In the present paper it is shown that this bound is close in order to the exact one. In particular, in case $d=n$ the construction provides a double-exponential (in $n$) number of vectors of multiplicities.
Received: 03.08.2000
Citation:
D. Yu. Grigor'ev, “Double-exponential growth of the number of vectors of solutions of polynomial systems”, Computational complexity theory. Part VI, Zap. Nauchn. Sem. POMI, 277, POMI, St. Petersburg, 2001, 47–52; J. Math. Sci. (N. Y.), 118:2 (2003), 4963–4965
Linking options:
https://www.mathnet.ru/eng/znsl1428 https://www.mathnet.ru/eng/znsl/v277/p47
|
Statistics & downloads: |
Abstract page: | 163 | Full-text PDF : | 68 |
|