Shortcuts
Top of page (Alt+0)
Page content (Alt+9)
Page menu (Alt+8)
Your browser does not support javascript, some WebOpac functionallity will not be available.
.
Default
.
PageMenu
-
Main Menu
-
Simple Search
.
Advanced Search
.
Journal Search
.
Refine Search Results
.
Preferences
.
Search Menu
Simple Search
.
Advanced Search
.
New Items Search
.
Journal Search
.
Refine Search Results
.
Bottom Menu
Help
Italian
.
English
.
German
.
New Item Menu
New Items Search
.
New Items List
.
Links
SISSA Library
.
ICTP library
.
Italian National web catalog (SBN)
.
Trieste University web catalog
.
Udine University web catalog
.
© LIBERO v6.4.1sp220816
Page content
You are here
:
Catalogue Display
Catalogue Display
Completeness and Reduction in Algebraic Complexity Theory
.
Bookmark this Record
Catalogue Record 43622
.
.
Author info on Wikipedia
.
.
LibraryThing
.
.
Google Books
.
.
Amazon Books
.
Catalogue Information
Catalogue Record 43622
.
Reviews
Catalogue Record 43622
.
British Library
Resolver for RSN-43622
Google Scholar
Resolver for RSN-43622
WorldCat
Resolver for RSN-43622
Catalogo Nazionale SBN
Resolver for RSN-43622
GoogleBooks
Resolver for RSN-43622
ICTP Library
Resolver for RSN-43622
.
Share Link
Jump to link
Catalogue Information
Field name
Details
Dewey Class
518
Title
Completeness and Reduction in Algebraic Complexity Theory ([EBook] /) / by Peter Bürgisser.
Author
Bürgisser, Peter
Other name(s)
SpringerLink (Online service)
Publication
Berlin, Heidelberg : : Springer Berlin Heidelberg : : Imprint: Springer, , 2000.
Physical Details
XII, 168 p. : online resource.
Series
Algorithms and computation in mathematics
1431-1550 ; ; 7
ISBN
9783662041796
Summary Note
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.:
Contents note
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 Notation.
System details note
Online access to this digital book is restricted to subscription institutions through IP address (only for SISSA internal users)
Internet Site
http://dx.doi.org/10.1007/978-3-662-04179-6
Links to Related Works
Subject References:
Algebra
.
Computational Mathematics and Numerical Analysis
.
Computer mathematics
.
Computers
.
Mathematics
.
Theory of Computation
.
Authors:
Bürgisser, Peter
.
Corporate Authors:
SpringerLink (Online service)
.
Series:
Algorithms and computation in mathematics
.
Classification:
518
.
.
ISBD Display
Catalogue Record 43622
.
Tag Display
Catalogue Record 43622
.
Related Works
Catalogue Record 43622
.
Marc XML
Catalogue Record 43622
.
Add Title to Basket
Catalogue Record 43622
.
Catalogue Information 43622
Beginning of record
.
Catalogue Information 43622
Top of page
.
Download Title
Catalogue Record 43622
Export
This Record
As
Labelled Format
Bibliographic Format
ISBD Format
MARC Format
MARC Binary Format
MARCXML Format
User-Defined Format:
Title
Author
Series
Publication Details
Subject
To
File
Email
Reviews
This item has not been rated.
Add a Review and/or Rating
43622
1
43622
-
2
43622
-
3
43622
-
4
43622
-
5
43622
-
Quick Search
Search for