ISSN:
1432-0622
Keywords:
Real algebraic numbers
;
Parallel algebraic complexity
;
NC complexity
;
Thom's lemma
;
Systems of polynomial inequalities
;
Sturm theory
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract Characterizing real algebraic numbers by a sign-sequence (according to Thom's lemma), using a variant of Ben Or Kozan and Reif algorithm for reducing the solving of systems of polynomial inequalities to the problem of counting real zeroes satisfying one polynomial inequality, and using a multivariate Sturm theory generalizing Hermite quadratic forms method for counting real zeroes, we prove that the computations on real algebraic numbers are in NC.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01387193
Permalink