Completeness and reduction in algebraic complexity theory / Peter Brgisser.
By: Bürgisser, Peter
.
Material type: ![materialTypeLabel](/opac-tmpl/lib/famfamfam/BK.png)
![](/opac-tmpl/bootstrap/images/filefind.png)
Item type | Current library | Call number | Copy number | Status | Date due | Barcode | Item holds |
---|---|---|---|---|---|---|---|
General Lending | MTU Bishopstown Library Lending | 511.3 (Browse shelf(Opens below)) | 1 | Available | 00075292 |
Enhanced descriptions from Syndetics:
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.
Includes bibliographical references (pages 149-157) and index.
Introduction -- Valiant's algebraic model of NP-completeness -- Some complete families of polynomials -- Cook's versus Valiant's hypothesis -- The structure of Valiant's complexity classes -- Fast evaluation of representations of general linear groups -- The complexity of immanants -- Separation results and future directions.
Table of contents provided by Syndetics
- 1 Introduction.
- 2 Valiant's Algebraic Model of NP-Completeness.
- 3 Some Complete Families of Polynomials.
- 4 Cook's versus Valiant's Hypothesis.
- 5 The Structure of Valiant'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 Notations.
- Index