RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 1999 Volume 256, Pages 168–211 (Mi znsl977)

This article is cited in 9 papers

Strong version of the basic deciding algorithm for the existential theory of real fields

A. L. Chistov

St. Petersburg Institute for Informatics and Automation of RAS

Abstract: Let $U$ be a real algebraic variety in $n$-dimensional affine space which is a set of all zeroes of a family of polynomials of degrees less than $d$. In the case when $U$ is bounded (it is the main case) an algorithm of polynomial complexity is described for constructing a subset of $U$ with the number of elements bounded from above by $d^n$ which for every $s$ has a non–empty intersection with every cycle with coefficients from ${\mathbb Z}/2{\mathbb Z}$ of dimension $s$ of the closure of the set of smooth points of dimension $s$ of $U$.

UDC: 519.5

Received: 15.01.1999


 English version:
Journal of Mathematical Sciences (New York), 2001, 107:5, 4265–4295

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024