A note on Rabin's width of a complete proof
type: Item
instance of: scholarly article
title: A note on Rabin's width of a complete proof
zbMATH Open document ID: 0806.68062
DOI: 10.1007/BF01205053
author: Tomas Recio
author: J. L. Montaña
author: Luis Miguel Pardo
published in: Computational Complexity
publication date: 1994-06-19T00:00:00Z
review text: The concept of generic width of a semi-algebraic set is introduced and used to obtain various lower bounds for decisional complexities. Rabin considered the optimality of algorithms solving the membership problem for convex sets defined by the simultaneous positivity of linear forms and gave several applications. In the paper, a rigorous proof of a theorem of Rabin is given and insufficiencies in the original Rabin's proof are discussed (it is not true that the closure of a semi-algebraic set can be simply defined by relaxing inequalities on the polynomials defining it). The method presented in the paper has new applications to more general situations than linear ones. Convincing lower bounds for several important decision problems in real algebraic geometry (like the existence of a real root) or in computational geometry (directed oriented convex problem) are obtained.
reviewed by: Marie-Françoise Roy
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 14P20
Mathematics Subject Classification ID: 14P10
zbMATH DE Number: 591235
zbMATH Keywords: generic width
zbMATH Keywords: decisional complexities
MaRDI profile type: Publication
cites work: Q3996250
cites work: Sur la factorialite des anneaux de fonctions de Nash
cites work: Q3926035
cites work: Q3973344
cites work: Proving simultaneous positivity of linear forms
cites work: Sur l'anneau des fonctions de Nash globales
full work available at URL: https://doi.org/10.1007/bf01205053
OpenAlex ID: W2069741443
description: scientific article; zbMATH DE number 591235