Computability and Complexity Theory

Front Cover
Springer Science & Business Media, 2001 - Computers - 194 pages
This volume introduces materials that are the core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations and subsequent chapters moving from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability round off the work, which focuses on the limitations of computability and the distinctions between feasible and intractable.Topics and features:*Concise, focused materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes*Contains information that otherwise exists only in research literature and presents it in a unified, simplified manner; for example, about complements of complexity classes, search problems, and intermediate problems in NP*Provides key mathematical background information, including sections on logic and number theory and algebra*Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential and practical learning tool.
 

What people are saying - Write a review

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

Contents

II
1
IV
2
V
3
VI
4
VII
6
VIII
8
X
10
XI
11
XLII
80
XLIII
86
XLIV
87
XLV
90
XLVI
97
XLVII
105
XLVIII
107
XLIX
111

XIII
15
XIV
17
XV
22
XVI
23
XVII
26
XVIII
28
XIX
29
XX
31
XXI
34
XXII
36
XXIII
39
XXIV
41
XXVI
43
XXVII
46
XXVIII
47
XXIX
50
XXX
53
XXXI
55
XXXII
57
XXXIII
59
XXXIV
66
XXXV
69
XXXVI
70
XXXVII
72
XXXVIII
74
XXXIX
76
XL
77
XLI
78
L
113
LI
115
LII
116
LIII
120
LIV
122
LV
123
LVI
124
LVII
126
LVIII
128
LIX
130
LX
136
LXI
142
LXII
145
LXIII
147
LXIV
151
LXV
153
LXVI
158
LXVII
161
LXVIII
162
LXIX
170
LXXI
174
LXXII
175
LXXIII
179
LXXV
181
LXXVI
187
LXXVII
189
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 183 - T. Baker, J. Gill, and R. Solovay. Relativizations of the P = NP question.
Page 78 - A transducer T is a nondeterministic Turing machine with a read-only input tape, a write-only output tape, and accepting states in the usual manner. T computes a value y on an input string x if there is an accepting computation of T on x for which y is the final contents of T's output tape. Such transducers compute partial, multivalued functions.
Page 183 - JL Balcazar and U. Schoning. Bi-immune sets for complexity classes. Mathematical Systems Theory 18:1-10, 1985.
Page 182 - S is sparse if there is a polynomial p such that for all n, the set {x & S : \x\ < n} has size at most p(n).

Bibliographic information