NC algorithms for real algebraic numbers

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

doi:10.1007/BF01387193

NC algorithms for real algebraic numbers

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

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	79-98
Number of pages	20
Journal	Applicable Algebra in Engineering, Communication and Computing
Volume	3
Issue number	2
DOIs	https://doi.org/10.1007/BF01387193
State	Published - 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

Access to Document

10.1007/BF01387193

Cite this

@article{097d46b51012449cb232ea891f113b76,

title = "NC algorithms for real algebraic numbers",

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.",

keywords = "NC complexity, Parallel algebraic complexity, Real algebraic numbers, Sturm theory, Systems of polynomial inequalities, Thom's lemma",

author = "F. Cucker and H. Lanneau and B. Mishra and P. Pedersen and Roy, {M. F.}",

year = "1992",

month = jun,

doi = "10.1007/BF01387193",

language = "English (US)",

volume = "3",

pages = "79--98",

journal = "Applicable Algebra in Engineering, Communication and Computing",

issn = "0938-1279",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - NC algorithms for real algebraic numbers

AU - Cucker, F.

AU - Lanneau, H.

AU - Mishra, B.

AU - Pedersen, P.

AU - Roy, M. F.

PY - 1992/6

Y1 - 1992/6

N2 - 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.

AB - 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.

KW - NC complexity

KW - Parallel algebraic complexity

KW - Real algebraic numbers

KW - Sturm theory

KW - Systems of polynomial inequalities

KW - Thom's lemma

UR - http://www.scopus.com/inward/record.url?scp=0038963157&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038963157&partnerID=8YFLogxK

U2 - 10.1007/BF01387193

DO - 10.1007/BF01387193

M3 - Article

AN - SCOPUS:0038963157

SN - 0938-1279

VL - 3

SP - 79

EP - 98

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

IS - 2

ER -

NC algorithms for real algebraic numbers

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this