In his study of Newton's root approximation method, Smale (1985) defined the Newtonian graph of a complex univariate polynomialf. The vertices of this graph are the roots offandf′and the edges are the degenerate curves of flow of the Newtonian vector fieldNf(z) = −f(z)/f′(z). The embedded edges of this graph form the boundaries of root basins in Newton's root approximation method. The graph defines a treelike relation on the roots offandf′, similar to the linear order whenfhas only real roots. We give an efficient algebraic algorithm based on cell decomposition to compute the Newtonian graph. The resulting structure can be used to query whether two points in C are in the same basin. This suggests a modified version of Newton's method in which one can test whether a step has crossed a basin boundary. We show that this modified version does not necessarily converge to a root. Stefánsson (1995) has recently extended this algorithm to handle rational and algebraic functions without a significant increase in complexity. He has shown that the Newtonian graph tesselates the associated Riemann surface and can be used in conjunction with Euler's formula to give anNCalgorithm to calculate the genus of an algebraic curve.

A system of set constraints is a system of expressions E/spl sube/F where E and F describe sets of ground terms over a ranked alphabet. Aiken et al. (1993) classified the complexity of such systems. In A. aiken et al. (1993), it was shown that if negative constraints Enot/spl sube/F were allowed, then the problem as decidable. This was done by reduction to a Diophantine problem, the nonlinear reachability problem, which was shown to be decidable. We show that nonlinear reachability is NP-complete. By bounding the reduction of A. aiken et al. (1993), we conclude that systems of set constraints allowing negative constraints are NEXPTIME-complete.>