Name
Abstract | ||
|---|---|---|
We show lower bounds for depth of arithmetic networks over algebraically closed fields, real closed fields and the field of the rationals. The parameters used are either the degree or the number of connected components. These lower bounds allow us to show the inefficiency of arithmetic networks to parallelize several natural problems. For instance, we show a vn lower bound for parallel time of the Knapsack problem over the reals and also that the computation of the “integer part” is not well parallelizable by arithmetic networks. Over the rationals we obtain results of similar order and that the Knapsack has an vn lower bound for the parallel time measured by networks. A simply exponential lower bound for the parallel time of quantifier elimination is also shown. Finally, separations among classesPKandNCKare available for fieldsK in the above cases. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/BF01270397 | Appl. Algebra Eng. Commun. Comput. |
Keywords | Field | DocType |
Parallel complexity,Algebraic complexity theory,Arithmetic networks,Constructible and semialgebraic sets,Degree and connected components | Quantifier elimination,Parallelizable manifold,Integer,Discrete mathematics,Rational number,Combinatorics,Upper and lower bounds,Arithmetic,Connected component,Knapsack problem,Mathematics,Algebraically closed field | Journal |
Volume | Issue | ISSN |
4 | 1 | 0938-1279 |
Citations | PageRank | References |
29 | 2.30 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josè L. Montaña | 1 | 82 | 15.50 |
| Luis Miguel Pardo | 2 | 141 | 15.63 |