Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/92360
Title: Polynomial-time computing over quadratic maps I : sampling in real algebraic sets
Authors: Grigoriev, Dima.
Pasechnik, Dmitrii V.
Keywords: DRNTU::Science::Mathematics::Applied mathematics
Issue Date: 2005
Source: Grigoriev, D., & Pasechnik, D. V. (2005). Polynomial-time computing over quadratic maps I: sampling in real algebraic sets. Computational Complexity, 14, 20-52.
Series/Report no.: Computational complexity
Abstract: Given a quadratic map Q : Kn → Kk defined over a computable subring D of a real closed field K, and p ∈ D[Y1,..., Yk] of degree d we consider the zero set Z = Z(p(Q(X)),Kn) ⊆ Kn of p(Q(X1,..., Xn)) ∈ D[X1,..., Xn]. We present a procedure that com¬putes, in (dn)O(k) arithmetic operations in D, a set S of (real univariate representations of) sampling points in Kn that intersects nontrivially each connected component of Z. As soon as k = o(n), this is faster than the standard methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure is only capable of deciding in nO(k2) operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y ) = Σi Y i2 and homogeneous Q. A by-product of our procedure is a bound (dn)O(k) on the number of connected components of Z. The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending K by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.
URI: https://hdl.handle.net/10356/92360
http://hdl.handle.net/10220/6869
DOI: http://dx.doi.org/10.1007/s00037-005-0189-7
Rights: © 2005 Birkhäuser Verlag AG, Basel. This is the author created version of a work that has been peer reviewed and accepted for publication by Computational Complexity, Birkhäuser Verlag AG, Basel. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at the following DOI: http://dx.doi.org/10.1007/s00037-005-0189-7.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
12. POLYNOMIAL-TIME COMPUTING OVER.pdf397.98 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.