<電子ブック>
Completeness and Reduction in Algebraic Complexity Theory / by Peter Bürgisser
(Algorithms and Computation in Mathematics ; 7)
版 | 1st ed. 2000. |
---|---|
出版者 | (Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer) |
出版年 | 2000 |
本文言語 | 英語 |
大きさ | XII, 168 p : online resource |
著者標目 | *Bürgisser, Peter author SpringerLink (Online service) |
件 名 | LCSH:Mathematics -- Data processing
全ての件名で検索
LCSH:Computer science LCSH:Algebra FREE:Computational Mathematics and Numerical Analysis FREE:Theory of Computation FREE:Algebra |
一般注記 | 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 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 HTTP:URL=https://doi.org/10.1007/978-3-662-04179-6 |
目次/あらすじ
所蔵情報を非表示
電子ブック | 配架場所 | 資料種別 | 巻 次 | 請求記号 | 状 態 | 予約 | コメント | ISBN | 刷 年 | 利用注記 | 指定図書 | 登録番号 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
電子ブック | オンライン | 電子ブック |
|
Springer eBooks | 9783662041796 |
|
電子リソース |
|
EB00227056 |
類似資料
この資料の利用統計
このページへのアクセス回数:3回
※2017年9月4日以降