Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations

✍ Scribed by Dima Grigoriev

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 273 KB
• Volume: 13
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.1997.0436

✦ Synopsis

The complexity lower bound of ( p log N) was obtained [12,14] for recognizing a semialgebraic set with N connected components by some parallel computational models, like the accepting network or the algebraic PRAM. It is unknown whether a parallel computation has an advantage versus its sequential counterpart for this sort of problem, i.e., whether it could recognize a semialgebraic set faster than within complexity O(log N) (the complexity lower bound for sequential algebraic computation trees [1,15]). We introduce a computational model called the multiprocessor algebraic computation which extends the notions of accepting network and algebraic PRAM.

For this model an ( p log N) complexity lower bound still holds. We design a multiprocessor algebraic computation which recognizes a linear complex in (i.e., a set given by a Boolean combination of N linear inequalities) within the complexity O( p log N log log N) for small n.