Boolean Functions and Computation Models

Front Cover
Springer Science & Business Media, Sep 19, 2002 - Computers - 602 pages
0 Reviews
The foundations of computational complexity theory go back to Alan Thring in the 1930s who was concerned with the existence of automatic procedures deciding the validity of mathematical statements. The first example of such a problem was the undecidability of the Halting Problem which is essentially the question of debugging a computer program: Will a given program eventu ally halt? Computational complexity today addresses the quantitative aspects of the solutions obtained: Is the problem to be solved tractable? But how does one measure the intractability of computation? Several ideas were proposed: A. Cobham [Cob65] raised the question of what is the right model in order to measure a "computation step" , M. Rabin [Rab60] proposed the introduction of axioms that a complexity measure should satisfy, and C. Shannon [Sha49] suggested the boolean circuit that computes a boolean function. However, an important question remains: What is the nature of computa tion? In 1957, John von Neumann [vN58] wrote in his notes for the Silliman Lectures concerning the nature of computation and the human brain that . . . logics and statistics should be primarily, although not exclusively, viewed as the basic tools of 'information theory'. Also, that body of experience which has grown up around the planning, evaluating, and coding of complicated logical and mathematical automata will be the focus of much of this information theory. The most typical, but not the only, such automata are, of course, the large electronic computing machines.
 

What people are saying - Write a review

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

Contents

I
xiii
III
xiv
IV
5
V
6
VI
9
VII
10
VIII
15
IX
19
LXXVII
233
LXXVIII
234
LXXIX
236
LXXX
237
LXXXI
239
LXXXII
240
LXXXIII
241
LXXXIV
245

X
22
XI
28
XII
29
XIII
30
XIV
32
XV
33
XVI
37
XVII
43
XVIII
44
XIX
46
XX
51
XXI
52
XXIII
53
XXIV
54
XXV
59
XXVII
61
XXVIII
63
XXIX
66
XXX
75
XXXI
76
XXXII
88
XXXIII
93
XXXIV
94
XXXV
97
XXXVI
100
XXXVII
105
XXXVIII
108
XXXIX
122
XLI
127
XLII
130
XLIV
133
XLV
135
XLVI
138
XLVII
139
XLVIII
141
XLIX
143
L
144
LI
146
LII
148
LIII
153
LIV
154
LV
160
LVI
162
LVII
166
LVIII
170
LIX
172
LX
176
LXI
182
LXII
183
LXIII
192
LXV
205
LXVI
207
LXVII
210
LXVIII
211
LXIX
212
LXX
215
LXXI
216
LXXII
222
LXXIII
224
LXXIV
227
LXXV
228
LXXVI
230
LXXXV
247
LXXXVI
253
LXXXVII
255
LXXXVIII
257
LXXXIX
265
XC
266
XCI
269
XCII
277
XCIII
283
XCIV
289
XCV
294
XCVI
298
XCVII
304
XCVIII
306
XCIX
314
C
322
CI
324
CII
330
CIII
335
CIV
341
CV
343
CVI
346
CVII
351
CVIII
353
CIX
357
CX
364
CXI
368
CXII
370
CXIII
391
CXIV
396
CXV
401
CXVI
403
CXVII
404
CXVIII
411
CXIX
413
CXX
422
CXXI
425
CXXII
431
CXXIII
432
CXXIV
435
CXXV
436
CXXVI
448
CXXVII
456
CXXVIII
463
CXXIX
468
CXXX
476
CXXXI
485
CXXXII
486
CXXXIII
487
CXXXIV
495
CXXXVI
500
CXXXVII
509
CXXXVIII
525
CXXXIX
552
CXL
553
CXLI
554
CXLII
556
CXLIII
562
CXLIV
563
CXLV
567
CXLVI
589
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page v - Neumann sought a theory of the organization of automata which would be based on "that body of experience which has grown up around the planning, evaluating, and coding of complicated logical and mathematical automata" *) and which would have applications in the design and programming of digital computers. He outlined the general nature of this proposed automata theory : its materials, some of its problems, what it would be like, and the form of its mathematics. He began a comparative study of artificial...
Page 572 - MT Chao and J. Franco, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiable problem, Inf.

References to this book

Komplexitatstheorie
Ingo Wegener
No preview available - 2003
All Book Search results »