Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6830
Title: The Complexity of Quantifier Elimination in the Theory of an Algebraically Closed Field
Authors: Ierardi, Doug J.
Keywords: computer science
technical report
Issue Date: Aug-1989
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1030
Abstract: This thesis addresses several classic problems in algebraic and symbolic computation related to the solvability of systems of polynomial equations. We develop a parallel algebraic procedure for deciding when a set of multivariate polynomial equations with coefficients in an arbitrary field $K$ have a common solution in an algebraic closure of this field. All computation required by these algorithms takes place over $K$, the field of definition, and hence does not require explicit construction or approximation of solutions. The decision procedure is subsequently extended to yield an algorithm for deciding when solutions exist for arbitrary Boolean combinations of polynomial equations over an algebraically closed field. Modifications are introduced to compute projections of algebraic and semi-algebraic sets, producing an exponential-space algorithm for determining the truth of sentences in the theory of an arbitrary algebraically closed field. In addition, this algorithm can be executed in polynomial space (PSPACE) when restricted to sentences with a bounded number of quantifier alternations. The algebraic nature of the construction also allows us to develop naturally a quantifier elimination procedure for formulas in this theory within similar time and space bounds. Finally, we show that these results are nearly optimal in a common model of parallel arithmetic computation. We also show how these methods can be used to compute the dimension of an arbitrary algebraic set. A variety of other applications-including the construction and approximation of solutions for systems of multivariate polynomial equations and the isolation of real zones-are investigated.
URI: http://hdl.handle.net/1813/6830
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
89-1030.pdf9.73 MBAdobe PDFView/Open
89-1030.ps1.93 MBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us