Add to ORKGWe show that computing the dimension of a semi-algebraic set of R^n is an NP-complete problem in the Blum-Shub-Smale model of computation over the reals. Since this problem is easily seen to be NPR-hard, the main ingredient of the proof is an NPR algorithm for computing the dimension.On montre que le calcul de la dimension d'un ensemble semi-algébrique de R^n est un problème NP-complet dans le modèle de Blum-Shub-Smale de calcul sur les nombres réels. Puisqu'il est facile de voir que ce problème est NPR-dur, le principal ingrédient de la preuve est un algorithme NPR de calcul de la dimension
We study the complexity of second-order indefinite elliptic problems - div (a u) + bu=ƒ (with homog...
AbstractWe study formal Laurent series which are better approximated by their Oppenheim convergents....
Let F be a class of functions defined on a d-dimensional domain. Our task is to compute H m -norm ϵ-...
We show that proving lower bounds in algebraic models of computation may not be easier than in the s...
The Table Maker's Dilemma is the problem of always getting correctly rounded results when computing ...
In this paper we apply for the first time a new method for multivariate equation solving which was d...
We are interested in the complexity of the Poisson problem with homogeneous Dirichlet boundary condi...
The $k$-set agreement problem is a generalization of the uniform consensus problem: each process pro...
Let $S$ be a set of $n$ points in $R^d$, and let each point $p$ of $S$ have a positive weight $w(p)$...
The objective of this paper is to show how the recently proposed method by Giusti, Heintz, Morais, M...
AbstractWe show strict lower bounds for the complexity of several model checking problems for BPA (B...
In this paper, a set of definitions describing general real number representation systems is present...
We prove that the topological space szd, proposed in is path-connected and has infinite dimension. T...
Blum, Cucker, Shub and Smale have shown that the problem ``$\p = \np$~?'' has the same answer in all...
AbstractNotational definitions are pervasive in mathematical practic and are therefore supported in ...
We study the complexity of second-order indefinite elliptic problems - div (a u) + bu=ƒ (with homog...
AbstractWe study formal Laurent series which are better approximated by their Oppenheim convergents....
Let F be a class of functions defined on a d-dimensional domain. Our task is to compute H m -norm ϵ-...
We show that proving lower bounds in algebraic models of computation may not be easier than in the s...
The Table Maker's Dilemma is the problem of always getting correctly rounded results when computing ...
In this paper we apply for the first time a new method for multivariate equation solving which was d...
We are interested in the complexity of the Poisson problem with homogeneous Dirichlet boundary condi...
The $k$-set agreement problem is a generalization of the uniform consensus problem: each process pro...
Let $S$ be a set of $n$ points in $R^d$, and let each point $p$ of $S$ have a positive weight $w(p)$...
The objective of this paper is to show how the recently proposed method by Giusti, Heintz, Morais, M...
AbstractWe show strict lower bounds for the complexity of several model checking problems for BPA (B...
In this paper, a set of definitions describing general real number representation systems is present...
We prove that the topological space szd, proposed in is path-connected and has infinite dimension. T...
Blum, Cucker, Shub and Smale have shown that the problem ``$\p = \np$~?'' has the same answer in all...
AbstractNotational definitions are pervasive in mathematical practic and are therefore supported in ...
We study the complexity of second-order indefinite elliptic problems - div (a u) + bu=ƒ (with homog...
AbstractWe study formal Laurent series which are better approximated by their Oppenheim convergents....
Let F be a class of functions defined on a d-dimensional domain. Our task is to compute H m -norm ϵ-...