| Completeness and Reduction in Algebraic Complexity Theory Contributor(s): Bürgisser, Peter (Author) |
|
 |
ISBN: 3642086047 ISBN-13: 9783642086045 Publisher: Springer OUR PRICE: $104.49 Product Type: Paperback - Other Formats Published: December 2010 |
| Additional Information |
| BISAC Categories: - Mathematics | Logic - Mathematics | Discrete Mathematics - Mathematics | Number Systems |
| Dewey: 511.3 |
| Series: Algorithms and Computation in Mathematics |
| Physical Information: 0.39" H x 6.14" W x 9.21" (0.59 lbs) 168 pages |
| Descriptions, Reviews, Etc. |
| Publisher Description: One of the most important and successful theories in computational complex- ity is that of NP-completeness. This discrete theory is based on the Turing machine model and achieves a classification of discrete computational prob- lems according to their algorithmic difficulty. Turing machines formalize al- gorithms which operate on finite strings of symbols over a finite alphabet. By contrast, in algebraic models of computation, the basic computational step is an arithmetic operation (or comparison) of elements of a fixed field, for in- stance of real numbers. Hereby one assumes exact arithmetic. In 1989, Blum, Shub, and Smale 12] combined existing algebraic models of computation with the concept of uniformity and developed a theory of NP-completeness over the reals (BSS-model). Their paper created a renewed interest in the field of algebraic complexity and initiated new research directions. The ultimate goal of the BSS-model (and its future extensions) is to unite classical dis- crete complexity theory with numerical analysis and thus to provide a deeper foundation of scientific computation (cf. 11, 101]). Already ten years before the BSS-paper, Valiant 107, 110] had proposed an analogue of the theory of NP-completeness in an entirely algebraic frame- work, in connection with his famous hardness result for the permanent 108]. While the part of his theory based on the Turing approach (#P-completeness) is now standard and well-known among the theoretical computer science com- munity, his algebraic completeness result for the permanents received much less attention. |