Open AccessCounting connected components of a semialgebraic set in subexponential time
Author(s) -
D. Yu. Grigor'ev,
Nicolai Vorobjov
Publication year - 1992
Publication title -
computational complexity
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.973
H-Index - 39
eISSN - 1420-8954
pISSN - 1016-3328
DOI - 10.1007/bf01202001
Subject(s) - mathematics , integer (computer science) , set (abstract data type) , combinatorics , connected component , discrete mathematics , order (exchange) , component (thermodynamics) , value (mathematics) , computer science , physics , statistics , finance , economics , thermodynamics , programming language
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 typefi≥0 for 1≤i≤k, where the polynomialsfi∈ℤ[X1,...,Xn] have degrees deg(fi)
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom