A lower bound for the complexity of separating functions

DOI10.1216/RMJ-1984-14-4-925MaRDI QIDQ1070000zbMATH OpenFDO

Authors G. Stengle

Publication date 1984

Published in Rocky Mountain Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1216/RMJ-1984-14-4-925

zbMATH Keywords

complexitysemi-algebraic subsetsseparation theorem

Mathematics Subject Classification ID

Ordered fields (12J15) Real algebraic and real-analytic geometry (14Pxx)

Review text

Mostowski's separation theorem asserts that given two disjoint semi- algebraic subsets X and Y of \({\mathbb{R}}^ n\), there is a function f such that \(f(X)>0\) and \(f(Y)<0\) which is a sum of \(P_ i\sqrt{Q_ i}\), where \(P_ i\) and \(Q_ i\) are polynomials and \(Q_ i>0\). The result announced in this note is a lower bound for the number of summands needed: in \({\mathbb{R}}^{2^ M+1}\), one needs at least \(M+2\) summands in f for some X and Y.

Recommendations

• On the Mostowski number
• Séparation de semi-algébriques. (Separation of semi-algebraic sets)
• Separating families for semi-algebraic sets
• Separation of semialgebraic sets
• On the separation of basic semialgebraic sets by polynomials

Cited in

(2)

• A measure for semialgebraic sets related to Boolean complexity
• Séparation de semi-algébriques. (Separation of semi-algebraic sets)

This page was built for publication: A lower bound for the complexity of separating functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1070000)