Office of Academic Resources
Chulalongkorn University
Chulalongkorn University

Home / Help

AuthorBรผrgisser, Peter. author
TitleCompleteness and Reduction in Algebraic Complexity Theory [electronic resource] / by Peter Bรผrgisser
ImprintBerlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2000
Connect to
Descript XII, 168 p. online resource


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


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


Office of Academic Resources, Chulalongkorn University, Phayathai Rd. Pathumwan Bangkok 10330 Thailand

Contact Us

Tel. 0-2218-2929,
0-2218-2927 (Library Service)
0-2218-2903 (Administrative Division)
Fax. 0-2215-3617, 0-2218-2907

Social Network


facebook   instragram