Completeness and Reduction in Algebraic Complexity Theory (Algorithms and Computation in Mathematics)

by: Peter Bürgisser

(26 July 2000)

View FullText article

Amazon.ca, Amazon.de, Amazon.fr, Amazon.co.uk, Amazon.com, WorldCat

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algebra, complexity

Abstract

The theory of NP-completeness is a cornerstone of computational complexity. This monograph provides a thorough and comprehensive treatment of this concept in the framework of algebraic complexity theory. Many of the results presented are new and published for the first time. Topics include: complete treatment of Valiant's algebraic theory of NP-completeness, interrelations with the classical theory as well as the Blum-Shub-Smale model of computation, questions of structural complexity, fast evaluation of representations of general linear groups, and complexity of immanants. The book can be used at the advanced undergraduate or at the beginning graduate level in either mathematics or computer science.

@book{citeulike:2697553, abstract = {{The theory of NP-completeness is a cornerstone of computational complexity. This monograph provides a thorough and comprehensive treatment of this concept in the framework of algebraic complexity theory. Many of the results presented are new and published for the first time. Topics include: complete treatment of Valiant's algebraic theory of NP-completeness, interrelations with the classical theory as well as the Blum-Shub-Smale model of computation, questions of structural complexity, fast evaluation of representations of general linear groups, and complexity of immanants. The book can be used at the advanced undergraduate or at the beginning graduate level in either mathematics or computer science.}}, author = {B\"{u}rgisser, Peter }, citeulike-article-id = {2697553}, howpublished = {Hardcover}, isbn = {3540667520}, keywords = {algebra, complexity}, month = {July}, posted-at = {2008-04-21 19:12:08}, priority = {2}, publisher = {Springer}, title = {Completeness and Reduction in Algebraic Complexity Theory (Algorithms and Computation in Mathematics)}, url = {http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20\&path=ASIN/3540667520}, year = {2000} }

RIS record

TY - BOOK ID - citeulike:2697553 L3 - citeulike-article-id:2697553 TI - Completeness and Reduction in Algebraic Complexity Theory (Algorithms and Computation in Mathematics) PB - Springer SN - 3540667520 N2 - {The theory of NP-completeness is a cornerstone of computational complexity. This monograph provides a thorough and comprehensive treatment of this concept in the framework of algebraic complexity theory. Many of the results presented are new and published for the first time. Topics include: complete treatment of Valiant's algebraic theory of NP-completeness, interrelations with the classical theory as well as the Blum-Shub-Smale model of computation, questions of structural complexity, fast evaluation of representations of general linear groups, and complexity of immanants. The book can be used at the advanced undergraduate or at the beginning graduate level in either mathematics or computer science.} KW - algebra KW - complexity AU - Bürgisser, Peter PY - 2000/07/26/ UR - http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&path=ASIN/3540667520 ER -

RIS BibTeX