MTU Cork Library Catalogue

Syndetics cover image
Image from Syndetics

Completeness and reduction in algebraic complexity theory / Peter Brgisser.

By: Bürgisser, Peter, 1962-.
Material type: materialTypeLabelBookSeries: Algorithms and computation in mathematics ; vol.7.Publisher: Berlin ; New York : Springer, c2000Description: xii, 168 p. : ill. ; 24 cm.+ hbk.ISBN: 3540667520 .Subject(s): Computational complexityDDC classification: 511.3
Contents:
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.
Holdings
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
Total holds: 0

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

Powered by Koha