Some speed-ups and speed limits for real algebraic geometry. (English) Zbl 1008.14012
The main result of the paper (theorem 1.1) is an upper bound for the number of connected components of a semialgebraic set \(S\) defined by a system of polynomial equations and (strict) inequalities. The bound is linear in the normalized volume of a suitable polytope associated to the exponents of the monomials occurring in the equations defining \(S\) and single exponential in the number of inequalities taking part in the definition of \(S\). Moreover the bound contains an exponential extra factor of \(2^n\). In terms of the number of monomials occurring in the equations defining \(S\) this bound is single exponential, but independent of the degree of the equations (theorem 3.5).
Another result of the paper is an algorithm for the approximation of all real roots of a \(k\)-sparse univariate standard or exponential polynomial of degree \(d\) in a given interval. The execution time of this algorithm is linear in \(k\log d\) (theorem 1.3).
Finally the author enumerates a series of algorithmic problems of geometric nature whose solution in polynomial time would imply \(P=\text{NP}\).
Another result of the paper is an algorithm for the approximation of all real roots of a \(k\)-sparse univariate standard or exponential polynomial of degree \(d\) in a given interval. The execution time of this algorithm is linear in \(k\log d\) (theorem 1.3).
Finally the author enumerates a series of algorithmic problems of geometric nature whose solution in polynomial time would imply \(P=\text{NP}\).
Reviewer: Joos Heintz (Buenos Aires)
MSC:
| 14P10 | Semialgebraic sets and related spaces |
| 14Q20 | Effectivity, complexity and computational aspects of algebraic geometry |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
Software:
KroneckerReferences:
| [1] | Barna, B., Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln Algebraischer Gleichungen, Publ. Math. Debrecen, 4, 384-397 (1956) · Zbl 0073.10603 |
| [2] | S. Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, in Proceedings of the Twenty-Eight Annual ACM STOC, Philadelphia, PA, 1996, pp. 408-417, ACM, New York.; S. Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, in Proceedings of the Twenty-Eight Annual ACM STOC, Philadelphia, PA, 1996, pp. 408-417, ACM, New York. · Zbl 0917.14029 |
| [3] | Basu, S.; Pollack, R.; Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination, J. Assoc. Comput. Mach., 43, 1002-1045 (1996) · Zbl 0885.68070 |
| [4] | Benedetti, R.; Loeser, F.; Risler, J. J., Bounding the number of connected components of a real algebraic set, Discr. Comput. Geom., 6, 191-209 (1991) · Zbl 0743.14040 |
| [5] | Bernshtein, D. N.; Kushnirenko, A. G.; Khovanski, A. G., Newton polyhedra, Uspehi Mat. Nauk, 31, 201-202 (1976) · Zbl 0354.14001 |
| [6] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer-Verlag: Springer-Verlag Berlin/New York |
| [7] | Burago, Yu. D.; Zalgaller, V. A., Geometric Inequalities. Geometric Inequalities, Grundlehren der mathematischen Wissenschaften 285 (1988), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0633.53002 |
| [8] | Cucker, F.; Karpinski, M.; Koiran, P.; Lickteig, T.; Werther, K., On real Turing machines and toss coins, Proceedings of the 27th STOC (1995), ACM Press: ACM Press New York, p. 335-342 · Zbl 0938.68648 |
| [9] | Cucker, F.; Koiran, P.; Smale, S., A polynomial time algorithm for diophantine equations in one variable, J. Symbolic Comput., 27, 21-29 (1999) · Zbl 0920.11085 |
| [10] | Danilov, V. I.; Khovanski, A. G., Newton polyhedra and an algorithm for calculating Hodge-Deligne numbers, Math. USSR-Izv., 29, 279-298 (1987) · Zbl 0669.14012 |
| [11] | Dobkin, D.; Lipton, R., On the complexity of computations under varying sets of primitives, J. Comput. System Sci., 18, 86-91 (1979) · Zbl 0409.68023 |
| [12] | Dyer, M.; Gritzmann, P.; Hufnagel, A., On the complexity of computing mixed volumes, SIAM J. Comput., 27, 356-400 (1998) · Zbl 0909.68193 |
| [13] | Gel’fand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, Resultants, and Multidimensional Determinants (1994), Birkhäuser: Birkhäuser Boston · Zbl 0827.14036 |
| [14] | M. Giusti, G. Lecerf, and, B. Salvy, A Gröbner-free alternative to polynomial system solving, J. Complexity, to appear.; M. Giusti, G. Lecerf, and, B. Salvy, A Gröbner-free alternative to polynomial system solving, J. Complexity, to appear. · Zbl 1003.12005 |
| [15] | Gritzmann, P.; Klee, V., On the complexity of some basic problems in computational convexity II: Volume and mixed volumes, Polytopes: Abstract, Convex, and Computational, Scarborough, ON, 1993. Polytopes: Abstract, Convex, and Computational, Scarborough, ON, 1993, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 440 (1994), Kluwer Academic: Kluwer Academic Dordrecht, p. 373-466 · Zbl 0819.52008 |
| [16] | Giusti, M.; Heintz, J.; Morais, J. E.; Pardo, L. M., When polynomial equation systems can be “solved” fast?, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Paris, 1995. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Paris, 1995, Lecture Notes in Comput. Sci., 948 (1995), Springer-Verlag: Springer-Verlag Berlin, p. 205-231 · Zbl 0902.12005 |
| [17] | Hirsch, M., Differential Topology. Differential Topology, Graduate Texts in Mathematics, 33 (1994), Springer-Verlag: Springer-Verlag New York |
| [18] | Iliopoulos, C. S., Worst case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM J. Comput., 18, 658-669 (1989) · Zbl 0689.68059 |
| [19] | Khovanski, A., Fewnomials (1991), AMS Press: AMS Press Providence · Zbl 0728.12002 |
| [20] | Koiran, P., DIMACS Technical Report (July 1996) |
| [21] | P. Koiran, The real dimension problem is \(\textbf{NP}_R \); P. Koiran, The real dimension problem is \(\textbf{NP}_R \) · Zbl 1101.68565 |
| [22] | Lenstra, H. W., Finding small degree factors of Lacunary polynomials, Number Theory in Progress (Zakopane-Kóscielisko, 1997) (1999), de Gruyter: de Gruyter Berlin, p. 267-276 · Zbl 0949.11053 |
| [23] | Milnor, J., On the Betti numbers of real varieties, Proc. Amer. Math. Soc., 15, 275-280 (1964) · Zbl 0123.38302 |
| [24] | B. Mourrain, and, V. Y. Pan, Asymptotic acceleration of solving multivariate polynomial systems of equations, in, Proc. ACM STOC 1998.; B. Mourrain, and, V. Y. Pan, Asymptotic acceleration of solving multivariate polynomial systems of equations, in, Proc. ACM STOC 1998. · Zbl 1028.68216 |
| [25] | Mumford, D., Algebraic Geometry I: Complex Projective Varieties. Algebraic Geometry I: Complex Projective Varieties, Classics in Mathematics (1995), Springer-Verlag: Springer-Verlag Berlin · Zbl 0821.14001 |
| [26] | Neff, C. A.; Reif, J., An efficient algorithm for the complex roots problem, J. Complexity, 12, 81-115 (1996) · Zbl 0888.12005 |
| [27] | Oleinik, O.; Petrovsky, I., On the topology of real algebraic hypersurfaces, Izv. Akad. Akad. Nauk SSSR, 13, 389-402 (1949) · Zbl 0035.10204 |
| [28] | Papadimitriou, C. H., Computational Complexity (1995), Addison-Wesley: Addison-Wesley Reading · Zbl 0557.68033 |
| [29] | Plaisted, D. A., New NP-hard and NP-complete polynomial and integer divisibility problems, Theoret. Comput. Sci., 31, 125-138 (1984) · Zbl 0572.68027 |
| [30] | Richardson, D., Finding the number of distinct real roots of sparse polynomials of the form \(p(x\), \(x^n\)), Computational Algebraic Geometry, Nice, 1992. Computational Algebraic Geometry, Nice, 1992, Progr. Math., 109 (1993), Birkhäuser: Birkhäuser Boston, p. 225-233 · Zbl 0787.65028 |
| [31] | Rojas, J. M., Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert’s tenth problem, (Cucker, F.; Shub, M., Foundations of Computational Mathematics, Rio de Janeiro, January 1997 (1997), Springer-Verlag: Springer-Verlag Berlin/New York), 369-381 · Zbl 0911.13012 |
| [32] | Rojas, J. M., Intrinsic near quadratic complexity bounds for real multivariate root counting, Proceedings of the Sixth Annual European Symposium on Algorithms. Proceedings of the Sixth Annual European Symposium on Algorithms, Lecture Notes on Computer Science, 1461 (1998), Springer-Verlag: Springer-Verlag Berlin/New York, p. 127-138 · Zbl 0929.65028 |
| [33] | Rojas, J. M., On the complexity of diophantine geometry in low dimensions, Proceedings of the 31st Annual ACM STOC, May 1-4, 1999, Atlanta, Georgia (1999), ACM Press: ACM Press New York, p. 527-536 · Zbl 1345.68181 |
| [34] | Rojas, J. M., Solving degenerate sparse polynomial systems faster, J. Symbolic Comput., 28, 155-186 (1999) · Zbl 0943.65060 |
| [35] | J. M. Rojas, and, Y. Ye, Solving real fewnomials in logarithmic time, submitted for publication, 1999.; J. M. Rojas, and, Y. Ye, Solving real fewnomials in logarithmic time, submitted for publication, 1999. |
| [36] | Smith, H. J.S., On systems of integer equations and congruences, Philos. Trans., 151, 293-326 (1861) |
| [37] | Steele, J.; Yao, A., Lower bounds for algebraic decision trees, J. Algorithms, 3, 1-8 (1982) · Zbl 0477.68065 |
| [38] | Sturmfels, B., Sparse elimination theory, (Eisenbud, D.; Robbiano, L., Proc. Computat. Algebraic Geom. and Commut. Algebra, 1991, Cortona, Italy (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 377-396 |
| [39] | Thom, R., Sur l’homologie des variétés algébriques réelles, (Cairns, S., Differential and Combinatorial Topology (1965), Princeton University Press: Princeton University Press Princeton) · Zbl 0137.42503 |
| [40] | Ye, Y., Combining binary search and Newton’s method to compute real roots for a class of real functions, J. Complexity, 10, 271-280 (1994) · Zbl 0844.65045 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
