caa a22 4500 469034009 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920601xx s 000 0 eng 10.1007/BF01202001 doi (NATIONALLICENCE)springer-10.1007/BF01202001 Counting connected components of a semialgebraic set in subexponential time [Elektronische Daten] [D. Grigor'ev, N. Vorobjov Jr.] Let a semialgebraic set be given by a quantifier-free formula of the first-order theory of real closed fields withk atomic subformulae of the typef i≥0 for 1≤i≤k, where the polynomialsf i∈ℤ[X 1,...,X n] have degrees deg(f i)<d and the absolute value of each (integer) coefficient off i is at most 2M. An algorithm is exhibited which counts the number of connected components of the semialgebraic set in time (M (kd)n 20)O (1). Moreover, the algorithm allows us to determine whether any pair of points from the set are situated in the same connected component. Birkhäuser Verlag, 1992 68C25 nationallicence Grigor'ev D. V. A. Steklov Mathematical Institute, Academy of Sciences, Fontanka Embankment 27, 191011, St. Petersburg, Russia aut Vorobjov Jr. N. V. A. Steklov Mathematical Institute, Academy of Sciences, Fontanka Embankment 27, 191011, St. Petersburg, Russia aut computational complexity Birkhäuser-Verlag 2/2(1992-06-01), 133-186 1016-3328 2:2<133 1992 2 37 https://doi.org/10.1007/BF01202001 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01202001 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Grigor'ev D. V. A. Steklov Mathematical Institute, Academy of Sciences, Fontanka Embankment 27, 191011, St. Petersburg, Russia aut NATIONALLICENCE 700 1- Vorobjov Jr N. V. A. Steklov Mathematical Institute, Academy of Sciences, Fontanka Embankment 27, 191011, St. Petersburg, Russia aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/2(1992-06-01), 133-186 1016-3328 2:2<133 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer