Completeness and Reduction in Algebraic Complexity Theory

Front Cover
Springer Science & Business Media, Jun 21, 2000 - Mathematics - 168 pages
0 Reviews
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

I
1
II
3
III
4
IV
6
V
11
VII
16
IX
19
X
21
XXXII
76
XXXIII
81
XXXIV
82
XXXV
85
XXXVI
89
XXXVII
92
XXXVIII
96
XXXIX
105

XI
25
XII
30
XIII
34
XIV
37
XVI
39
XVII
41
XVIII
42
XIX
43
XX
44
XXI
48
XXII
50
XXIII
53
XXIV
55
XXV
61
XXVII
64
XXVIII
66
XXIX
68
XXX
70
XXXI
75
XL
107
XLI
109
XLII
112
XLIII
114
XLIV
115
XLV
117
XLVII
118
XLVIII
120
XLIX
121
L
126
LI
128
LII
135
LIII
139
LIV
141
LV
143
LVI
149
LVII
159
LVIII
163
Copyright

Other editions - View all

Common terms and phrases

References to this book

Bibliographic information