Author | Bรผrgisser, Peter. author |
---|---|

Title | Completeness and Reduction in Algebraic Complexity Theory [electronic resource] / by Peter Bรผrgisser |

Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2000 |

Connect to | http://dx.doi.org/10.1007/978-3-662-04179-6 |

Descript | XII, 168 p. online resource |

SUMMARY

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

CONTENT

1 Introduction -- 2 Valiantโ{128}{153}s Algebraic Model of NP-Completeness -- 3 Some Complete Families of Polynomials -- 4 Cookโ{128}{153}s versus Valiantโ{128}{153}s Hypothesis -- 5 The Structure of Valiantโ{128}{153}s Complexity Classes -- 6 Fast Evaluation of Representations of General Linear Groups -- 7 The Complexity of Immanants -- 8 Separation Results and Future Directions -- References -- List of Notation

Mathematics
Computers
Algebra
Computer mathematics
Mathematics
Computational Mathematics and Numerical Analysis
Theory of Computation
Algebra