The hardness of polynomial equation solving
Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intr...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2003
|
| Materias: | |
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 21839caa a22016697a 4500 | ||
|---|---|---|---|
| 001 | PAPER-4795 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203423.0 | ||
| 008 | 190411s2003 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-0042461761 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Castro, D. | |
| 245 | 1 | 4 | |a The hardness of polynomial equation solving |
| 260 | |c 2003 | ||
| 270 | 1 | 0 | |m Castro, D.; Depto. de Ciencias de la Computacion, E.U. Politécnica, Universidad de Alcalá, 28871 Alcalá de Henares, Spain; email: david.castro@uah.es |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M., Combinatorial hardness proofs for polynomial evaluation (1998) Lecture Notes in Computer Science, 1450, pp. 67-175. , in Proceedings 23rd International Symposium on Mathematical Foundations of Computer Science, MFoCS'98, (L. Brim et al., eds.); Springer-Verlag, Berlin | ||
| 504 | |a Aldaz, M., Matera, G., Montaña, J.L., Pardo, L.M., A new method to obtain lower bounds for polynomial evaluation (2001) Theoret. Comput. Sci., 259 (1-2), pp. 577-596 | ||
| 504 | |a Alder, A., Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht (1984), PhD thesis, Universität Zürich, Philosophische Fakultät II; Atiyah, M.F., MacDonald, J.G., (1969) Introduction to Commutative Algebra, , Addison-Wesley, Reading, MA | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real equation solving: The hypersurface case (1997) J. Complexity, 13 (1), pp. 5-27 | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Z., 238 (1), pp. 115-144 | ||
| 504 | |a Bayer, D., Mumford, D., What can be computed in algebraic geometry? (1993) Symposia Matematica, 34, pp. 1-49. , in Computational Algebraic Geometry and Commutative Algebra, (D. Eisenbud and L. Robbiano, eds.); Cambridge; Instituto Nazionale di Alta Matematica, Cambridge University Press, Cambridge | ||
| 504 | |a Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , Springer-Verlag, New York | ||
| 504 | |a Borel, E., La définition en mathématiques (1948) Les Grands Courants de la Pensée Mathématique, pp. 24-34. , Cahiers du Sud, Paris | ||
| 504 | |a Borodin, A., Time space tradeoffs (getting closer to the barriers?) (1993) 4th International Symposium on Algorithms and Computation, ISAAC '93, Hong Kong, December 15-17, 1993, Lecture Notes in Computer Science, 762, pp. 209-220. , Springer-Verlag, Berlin | ||
| 504 | |a Bruno, N., Heintz, J., Matera, G., Wachenchauzer, R., Functional programming concepts and straight-line programs in computer algebra (2002) Math. Comput. Simulation, 60 (6), pp. 423-473 | ||
| 504 | |a Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic complexity theory (1997) Grundlehren der Mathematischen Wissenschaften, 315. , Springer-Verlag, Berlin | ||
| 504 | |a Caniglia, L., Galligo, A., Heintz, J., Some new effectivity bounds in computational geometry (1989) Proceedings of AAECC-6, Lecture Notes in Computer Science, 357, pp. 131-152. , in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, (T. Mora et al., eds.); Springer-Verlag, Berlin | ||
| 504 | |a Canny, J., Some algebraic and geometric problems in PSPACE (1988) Proceedings 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, 2-4 May 1988, pp. 460-467. , ACM Press, New York | ||
| 504 | |a Castaño, B., Heintz, J., Llovet, J., Martínez, R., On the data structure straight-line program and its implementation in symbolic computation (2001) Math. Comput. Simulation, 51, pp. 497-528 | ||
| 504 | |a Castro, D., Hägele, K., Morais, J.E., Pardo, L.M., Kronecker's and Newton's approaches to solving: A first comparison (2001) J. Complexity, 17 (1), pp. 212-303 | ||
| 504 | |a Castro, D., Montaña, J.L., Pardo, L.M., San Martin, J., The distribution of condition numbers of rational data of bounded bit length (2002) Found. Comput. Math., 2 (1), pp. 1-52 | ||
| 504 | |a Chistov, A.L., Grigoriev, D.Y., Subexponential time solving systems of algebraic equations (1983), I, II. LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad; Cucker, F., Smale, S., Complexity estimates depending on condition and round-off error (1999) J. Assoc. Comput. Mach., 46 (1), pp. 113-184 | ||
| 504 | |a Davenport, J.H., Heintz, J., Real quantifier elimination is doubly exponential (1988) J. Symbolic Comput., 5, pp. 29-35 | ||
| 504 | |a Dickenstein, A., Fitchas, N., Giusti, M., Sessa, C., The membership problem for unmixed polynomial ideals is solvable in single exponential time (1991) Discrete Appl. Math., 33, pp. 73-94 | ||
| 504 | |a Fitchas, N., Galligo, A., Morgenstern, J., Algorithmes rapides en sequentiel et en parallele pour l'élimination des quantificateurs en Géométrie élementaire (1990) Pub. Math. Univ. Paris VII, 32, pp. 103-145. , in Seminaire sur les structures algébriques ordonnés (F. Delon, M. Dickmann, and D. Gondard, eds.); Paris | ||
| 504 | |a Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67 (1), pp. 1-14 | ||
| 504 | |a Fitchas, N., Giusti, M., Smietanski, F., Sur la complexité du théorème des zéros (1995) Proceedings 2nd International Conference on Non-Linear Optimization and Approximation, Approximation and Optimization, 8, pp. 247-329. , in Approximation and Optimization in the Caribbean II, (J. Guddat et al., ed.); Peter Lange Verlag, Frankfurt am Main | ||
| 504 | |a Fulton, W., (1984) Intersection Theory, , Springer-Verlag, Berlin | ||
| 504 | |a Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., (1994) Discriminants, Resultants, and Multidimensional Determinants, , Birkhäuser, Boston | ||
| 504 | |a Gianni, P., Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases (1989) Proceedings of AAECC-5, Menorca, Spain, June 15-19, 1987, Lecture Notes in Computer Science, 356, pp. 247-257. , in Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, (L. Huguet and A. Poli, eds.); Springer-Verlag, Berlin | ||
| 504 | |a Giusti, M., Hägele, K., Heintz, J., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for diophantine approximation (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317 | ||
| 504 | |a Giusti, M., Heintz, J., Algorithmes-disons rapides-pour la décomposition d' une variété algébrique en composantes irréductibles et équidimensionelles (1991) Proceedings of MEGA '90, Progress in Mathematics, 94, pp. 169-194. , Effective Methods in Algebraic Geometry (T. Mora and C. Traverso, eds.); Birkhäuser, Basel | ||
| 504 | |a Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Symposia Matematica, 34, pp. 216-256. , in Computational Algebraic Geometry and Commutative Algebra, (D. Eisenbud and L. Robbiano, eds.); Cambridge University Press, Cambridge | ||
| 504 | |a Giusti, M., Heintz, J., Kronecker's smart, little black-boxes (2001) FoCM'99, Oxford 1999, London Mathematical Society Lecture Notes Series, 284, pp. 69-104. , in Proceedings of Foundations of Computational Mathematics, (A. Iserles, R. Devore, and E. Süli, eds.); Cambridge University Press, Cambridge | ||
| 504 | |a Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124, pp. 101-146 | ||
| 504 | |a Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be solved fast? (1995) Proceedings AAECC-11, Lecture Notes in Computer Science, 948, pp. 205-231. , in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, (G. Cohen, H. Giusti, and T. Mora, eds.); Springer-Verlag, Berlin | ||
| 504 | |a Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., Le rôle des structures de données dans les problèmes d'élimination (1997) C. R. Acad. Sci. Paris, 325, pp. 1223-1228 | ||
| 504 | |a Giusti, M., Heintz, J., Sabia, J., On the efficiency of effective nullstellensätze (1993) Comput. Complexity, 3, pp. 56-95 | ||
| 504 | |a Giusti, M., Lecerf, G., Salvy, B., A gröbner-free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211 | ||
| 504 | |a Giusti, M., Schost, E., Solving some over-determined systems (1999) ISSAC'99, July 28-31, 1999, Vancouver, Canada, pp. 1-8. , in Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, (S. Dooley, ed.); ACM Press, New York | ||
| 504 | |a Goldberg, P., Jerrum, M., Bounding the vapnik-chervonenkis dimension of concept classes parametrized by real numbers (1995) Machine Learning, 18, pp. 131-148 | ||
| 504 | |a Grigoriev, D., Vorobjov Jr., N.N., Solving systems of polynomial inequalities in sub-exponential time (1988) J. Symbolic Comput., 5 (1-2), pp. 37-64 | ||
| 504 | |a Hägele, K., Morais, J.E., Pardo, L.M., Sombra, M., On the intrinsic complexity of the arithmetic nullstellensatz (2000) J. Pure Appl. Algebra, 146 (2), pp. 103-183 | ||
| 504 | |a Heintz, J., Definability bounds of first-order theories of algebraically closed fields (1979) FCT'79, pp. 160-166. , (Extended abstract), in Proceedings of Fundamentals of Computation Theory, (L. Budach, ed.); Berlin/Wendisch-Rietz, 1979; Akademie Verlag, Berlin | ||
| 504 | |a Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277 | ||
| 504 | |a Heintz, J., On the computational complexity of polynomials and bilinear mappings (1989) Proceedings of AAECC-5, Menorca, Spain, June 15-19, 1987, Lecture Notes in Computer Science, 356, pp. 269-300. , A survey in Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (L. Huguet and A. Poli, eds.); Springer-Verlag, Berlin | ||
| 504 | |a Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16 (1), pp. 70-109 | ||
| 504 | |a Heintz, J., Matera, G., Pardo, L.M., Wachenchauzer, R., The intrinsic complexity of parametric elimination methods (1998) Electron. J. SADIO, 1 (1), pp. 37-51 | ||
| 504 | |a Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Engng. Commun. Comput., 11 (4), pp. 239-296 | ||
| 504 | |a Heintz, J., Roy, M.-F., Solernó, P., On the complexity of semialgebraic sets (1989) Proceedings of the IFIP 11th World Computer Congress, San Francisco, USA, August 28-September 1, 1989, pp. 293-298. , in Information Processing 89, (G. Ritter, ed.); North-Holland/IFIP, Amsterdam | ||
| 504 | |a Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. France, 118 (1), pp. 101-126 | ||
| 504 | |a Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1982) International Symposium on Logic and Algorithmic, Zurich 1980, Monographie de l'Enseignement Mathématique, 30, pp. 237-254 | ||
| 504 | |a Heintz, J., Sieveking, M., Absolute primality of polynomials is decidable in random polynomial-time in the number of variables (1981) Lecture Notes in Computer Science, 115, pp. 16-28. , in ICALP 81: Proceedings 8th International Colloquium on Automata, Languages and Programming, Acre (Akko), Israel July 13-17, 1981, (Shimon Even and Oded Kariv, eds.); Springer-Verlag, Berlin | ||
| 504 | |a Ierardi, D., Quantifier elimination in the theory of an algebraically closed field (1989) Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, Washington, 15-17 May 1989, pp. 138-147. , ACM Press, New York | ||
| 504 | |a Iversen, B., Generic local structure of the morphisms in cummutative algebra (1973) Lecture Notes in Mathematics, 310. , Springer-Verlag, Berlin | ||
| 504 | |a Jerónimo, G., Sabia, J., On the number of sets definable by polynomials (2000) J. Algebra, 227 (2), pp. 633-644 | ||
| 504 | |a Kaltofen, E., Greatest common divisors of polynomials given by straight-line programs (1988) J. Assoc. Comput. Mach., 35 (1), pp. 231-264 | ||
| 504 | |a Kollár, J., (1999) Rational Curves on Algebraic Varieties, , Springer-Verlag, New York | ||
| 504 | |a Krick, T., Pardo, L.M., Une approche informatique pour l'approximation diophantienne (1994) C. R. Acad. Sci. Paris, 318 (1), pp. 407-412 | ||
| 504 | |a Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Proceedings of MEGA'94, Progress in Mathematics, 143, pp. 193-254. , in Algorithms in Algebraic Geometry and Applications, (L. González-Vega and T. Recio, eds.); Birkhäuser, Basel | ||
| 504 | |a Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Grössen (1882) J. Reine Angew. Math., 92, pp. 1-122 | ||
| 504 | |a Lang, S., (1958) Introduction to Algebraic Geometry, , Interscience, New York | ||
| 504 | |a Lang, S., (1993) Algebra, 3rd Ed., , Addison-Wesley, Reading, MA | ||
| 504 | |a Lecerf, G., (2000) Kronecker 0.16beta-2. Reference Manual, , http://kronecker.medicis.polytechnique.fr/, Laboratoire GAGE, École Polytechnique, Palaiseau, France | ||
| 504 | |a Lecerf, G., Quadratic Newton iteration for systems with multiplicity (2002) Found. Comput. Math., 2 (3), pp. 247-293 | ||
| 504 | |a Li, M., Vitányi, P., (1993) Introduction to Kolmogorov Complexity and Its Applications, , Springer-Verlag, Berlin | ||
| 504 | |a Matera, G., Probabilistic algorithms for geometric elimination (1999) Appl. Algebra Engrg. Commun. Comput., 9 (6), pp. 463-520 | ||
| 504 | |a Matsumura, H., (1980) Commutative Algebra, , Benjamin, New York | ||
| 504 | |a Montaña, J.L., Pardo, L.M., Lower bounds for arithmetic networks (1993) Appl. Algebra Engrg. Commun. Comput., 4 (1), pp. 1-24 | ||
| 504 | |a Mourrain, B., Pan, V., Solving special polynomial systems by using structural matrices and algebraic residues (1997) Proceedings Foundations of Computational Mathematics (FOCM'97), pp. 287-304. , (F. Crucker and M. Shub, eds.); Springer-Verlag, Berlin | ||
| 504 | |a Mumford, D., The red book of varieties and schemes (1988) Lecture Notes in Mathematics, 1358. , 1st edn., Springer-Verlag, Berlin | ||
| 504 | |a Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Proceedings of AAECC-11, Lecture Notes in Computer Science, 948, pp. 33-69. , in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, (G. Cohen, H. Giusti, and T. Mora, eds.); Springer-Verlag, Berlin | ||
| 504 | |a Paterson, M., Stockmeyer, L.J., On the number of nonscalar multiplications necessary to evaluate polynomials (1973) SIAM J. Comput., 2 (1), pp. 60-66 | ||
| 504 | |a Puddu, S., Sabia, J., An effective algorithm for quantifier elimination over algebraically closed fields using straight-line programs (1998) J. Pure Appl. Algebra, 129 (2), pp. 173-200 | ||
| 504 | |a Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals (1992) J. Symbol. Comput., 13 (3), pp. 255-300 | ||
| 504 | |a Rojas, J.M., Computing complex dimension faster and deterministically (2000), (extended abstract), preprint arXiv:math.AG/0005028; Schnorr, C.P., Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials (1978) Theoret. Comput. Sci., 7, pp. 251-261 | ||
| 504 | |a Schönhage, A., An elementary proof for strassen's degree bound (1976) Theoret. Comput. Sci., 3, pp. 267-272 | ||
| 504 | |a Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Engrg. Commun. Comput., 13 (5), pp. 349-393 | ||
| 504 | |a Shafarevich, I.R., (1994) Basic Algebraic Geometry, , Springer-Verlag | ||
| 504 | |a Shub, M., Smale, S., Complexity of Bézout's theorem I: Geometric aspects (1993) J. Amer. Math. Soc., 6 (2), pp. 459-501 | ||
| 504 | |a Shub, M., Smale, S., Complexity of Bézout's theorem II: Volumes and probabilities (1993) Progress in Mathematics, 109, pp. 267-285. , in Computational Algebraic Geometry, (F. Eyssette and A. Galligo, eds.); Birkhäuser, Basel | ||
| 504 | |a Shub, M., Smale, S., Complexity of Bézout's theorem III: Condition number and packing (1993) J. Complexity, 9, pp. 4-14 | ||
| 504 | |a Shub, M., Smale, S., Complexity of Bézout's theorem V: Polynomial time (1994) Theoret. Comput. Sci., 133, pp. 141-164 | ||
| 504 | |a Shub, M., Smale, S., Complexity of Bézout's theorem IV: Probability of success (1996) SIAM J. Numer. Anal., 33, pp. 141-164 | ||
| 504 | |a Strassen, V., Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationspolynomen (1973) Numer. Math., 2, pp. 238-251 | ||
| 504 | |a Strassen, V., Vermeidung von Divisionen (1973) Crelle J. Reine Angew. Math., 264, pp. 182-202 | ||
| 504 | |a Vapnik, V.N., The nature of statistical learning theory Statistics for Engineering and Information Science, 2nd Ed., , Springer-Verlag, New York, 2000 | ||
| 504 | |a Vogel, W., (1984) Results on Bezout's Theorem, , Tata Institute of Fundamental Research, Springer-Verlag, New York | ||
| 504 | |a Von Zur Gathen, J., Parallel arithmetic computations: A survey (1986) Lecture Notes in Computer Science, 233, pp. 93-112. , in Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, Bratislava, Czechoslovakia, August 25-29, 1996, (B. Rovan J. Gruska and J. Wiedermann, eds.); Springer-Verlag, Berlin | ||
| 504 | |a Von Zur Gathen, J., Parallel linear algebra (1993) Synthesis of Parallel Algorithms, , (John H. Reif, ed.), Morgan Kaufmann, Los Altas, CA | ||
| 504 | |a Weispfening, V., The complexity of linear problems in fields (1988) J. Symbolic Comput., 5, pp. 3-27 | ||
| 504 | |a Zariski, O., Theory and applications of holomorphic functions on algebraic varieties over arbitrary ground fields (1951) Mem. Amer. Math. Soc., 5, pp. 1-90 | ||
| 520 | 3 | |a Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intrinsic sequential time complexity of universal elimination procedures for arbitrary continuous data structures encoding input and output objects of elimination theory (i.e., polynomial equation systems) and admitting the representation of certain limit objects. Our main result is the following: let there be given such a data structure and together with this data structure a universal elimination algorithm, say P, solving arbitrary parametric polynomial equation systems. Suppose that the algorithm P avoids "unnecessary" branchings and that P admits the efficient computation of certain natural limit objects (as, e.g., the Zariski closure of a given constructible algebraic set or the parametric greatest common divisor of two given algebraic families of univariate polynomials). Then P cannot be a polynomial time algorithm. The paper contains different variants of this result and discusses their practical implications. |l eng | |
| 593 | |a Depto. de Ciencias de la Computacion, E.U. Politécnica, Universidad de Alcalá, 28871 Alcalá de Henares, Spain | ||
| 593 | |a Laboratoire GAGE, Ecole Polytechnique, F-91128 Palaiseau Cedex, France | ||
| 593 | |a Depto. Matematicas Estadistica Comp., Facultad de Ciencias, Universidad de Cantabria, E-39071 Santander, Spain | ||
| 593 | |a Departamento de Matemáticas, Fac. de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria Pabellon I, 1428 Buenos Aires, Argentina | ||
| 593 | |a CONICET, Argentina | ||
| 593 | |a Instituto de Desarrollo Humano, Univ. Nacional de General Sarmiento, Campus Universitario, Jose M. Gutierrez 1150, 1613 Los Polvor. Pcia. Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a COMPLEXITY |
| 690 | 1 | 0 | |a CONTINUOUS DATA STRUCTURE |
| 690 | 1 | 0 | |a ELIMINATION THEORY |
| 690 | 1 | 0 | |a HOLOMORPHIC AND CONTINUOUS ENCODING |
| 690 | 1 | 0 | |a POLYNOMIAL EQUATION SOLVING |
| 690 | 1 | 0 | |a ARITHMETIC CIRCUITS |
| 690 | 1 | 0 | |a BEZOUT NUMBER |
| 690 | 1 | 0 | |a ELIMINATION THEORY |
| 690 | 1 | 0 | |a GEOMETRIC OBJECTS |
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a DATA STRUCTURES |
| 690 | 1 | 0 | |a DIGITAL ARITHMETIC |
| 690 | 1 | 0 | |a ENCODING (SYMBOLS) |
| 690 | 1 | 0 | |a GEOMETRY |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 690 | 1 | 0 | |a PROBLEM SOLVING |
| 690 | 1 | 0 | |a TOPOLOGY |
| 690 | 1 | 0 | |a POLYNOMIALS |
| 650 | 1 | 7 | |2 spines |a ALGEBRA |
| 700 | 1 | |a Giusti, M. | |
| 700 | 1 | |a Heintz, J. | |
| 700 | 1 | |a Matera, G. | |
| 700 | 1 | |a Pardo, L.M. | |
| 773 | 0 | |d 2003 |g v. 3 |h pp. 347-420 |k n. 4 |p Found. Comput. Math. |x 16153375 |t Foundations of Computational Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-0042461761&doi=10.1007%2fs10208-002-0065-7&partnerID=40&md5=8d4ca47a62332b31743e3bfeccd94e00 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10208-002-0065-7 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_16153375_v3_n4_p347_Castro |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v3_n4_p347_Castro |y Registro en la Biblioteca Digital |
| 961 | |a paper_16153375_v3_n4_p347_Castro |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 65748 | ||