NC algorithms for real algebraic numbers

F. Cucker, H. Lanneau, B. Mishra, P. Pedersen, M. F. Roy

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)79-98
Number of pages20
JournalApplicable Algebra in Engineering, Communication and Computing
Volume3
Issue number2
DOIs
StatePublished - Jun 1992

Keywords

  • NC complexity
  • Parallel algebraic complexity
  • Real algebraic numbers
  • Sturm theory
  • Systems of polynomial inequalities
  • Thom's lemma

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics

Fingerprint Dive into the research topics of 'NC algorithms for real algebraic numbers'. Together they form a unique fingerprint.

Cite this