Geometric Problems Solvable in Single Exponential Time
作者： Joos Heintz , Teresa Krick , Marie-Françoise Roy , Pablo Solernó
关键词:
摘要: Let S be a semialgebraic set given by boolean combination of polynomial inequalities. We present an algorithmical method which solves in single exponential sequential time and parallel time, the following problems: computation dimension S. computation number semialgebraically connected components construction paths connecting points same component. computation distance to another finding realizing if they exist. computation “optical resolution” is closed (the pelotita bolon). computation integer Morse directions regular algebraic hypersurface.
springer.com
sci-hub.st 参考文章(21)
Marie-Françoise Roy, Joos Heintz, Pablo Solernó, On the Complexity of Semialgebraic Sets. ifip congress. pp. 293- 298 ,(1989)
Joos Heintz, Marie-Françoise Roy, Pablo Solernó, Sur la complexité du principe de Tarski-Seidenberg Bulletin de la Société mathématique de France. ,vol. 118, pp. 101- 126 ,(1990) , 10.24033/BSMF.2138
J. Bochnak, M. Coste, M-F Roy, Géométrie algébrique réelle Springer-Verlag. ,(1987)
Leandro Caniglia, André Galligo, Joos Heintz, Some new effectivity bounds in computational geometry Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. pp. 131- 151 ,(1989) , 10.1007/3-540-51083-4_54
Joos Heintz, Marie-Francoise Roy, Pablo Solernó, Single Exponential Path Finding in Semialgebraic Sets. Part 1: The Case of a Regular Bounded Hypersurface Applicable Algebra in Engineering, Communication and Computing. pp. 180- 196 ,(1990) , 10.1007/3-540-54195-0_50
J{ános Koll{ár, Sharp effective Nullstellensatz Journal of the American Mathematical Society. ,vol. 1, pp. 963- 975 ,(1988) , 10.1090/S0894-0347-1988-0944576-7
Michael Ben-Or, Dexter Kozen, John Reif, The complexity of elementary algebra and geometry Journal of Computer and System Sciences. ,vol. 32, pp. 251- 264 ,(1986) , 10.1016/0022-0000(86)90029-2
Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields Theoretical Computer Science. ,vol. 24, pp. 239- 277 ,(1983) , 10.1016/0304-3975(83)90002-6
M. Coste, M.F. Roy, Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets Journal of Symbolic Computation. ,vol. 5, pp. 121- 129 ,(1988) , 10.1016/S0747-7171(88)80008-7
W. Dale Brownawell, Bounds for the degrees in the Nullstellensatz Annals of Mathematics. ,vol. 126, pp. 577- 591 ,(1987) , 10.2307/1971361