| 书目名称 | Completeness and Reduction in Algebraic Complexity Theory |
| 编辑 | Peter Bürgisser |
| 视频video | |
| 概述 | Only monograph with the latest results in the field..Includes supplementary material: |
| 丛书名称 | Algorithms and Computation in Mathematics |
| 图书封面 |  |
| 描述 | 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 |
| 出版日期 | Book 2000 |
| 关键词 | NP-completeness; Notation; algebra; complexity; complexity theory |
| 版次 | 1 |
| doi | https://doi.org/10.1007/978-3-662-04179-6 |
| isbn_softcover | 978-3-642-08604-5 |
| isbn_ebook | 978-3-662-04179-6Series ISSN 1431-1550 |
| issn_series | 1431-1550 |
| copyright | Springer-Verlag Berlin Heidelberg 2000 |
发表于 2025-3-21 17:17:12
