Atjaunināt sīkdatņu piekrišanu

Computability and Complexity Theory 2nd ed. 2011 [Hardback]

1.00/5 (3 ratings by Goodreads)
,
  • Formāts: Hardback, 300 pages, height x width: 235x155 mm, weight: 641 g, XVI, 300 p., 1 Hardback
  • Sērija : Texts in Computer Science
  • Izdošanas datums: 09-Dec-2011
  • Izdevniecība: Springer-Verlag New York Inc.
  • ISBN-10: 1461406811
  • ISBN-13: 9781461406815
Citas grāmatas par šo tēmu:
  • Hardback
  • Cena: 78,14 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Standarta cena: 91,94 €
  • Ietaupiet 15%
  • Grāmatu piegādes laiks ir 3-4 nedēļas, ja grāmata ir uz vietas izdevniecības noliktavā. Ja izdevējam nepieciešams publicēt jaunu tirāžu, grāmatas piegāde var aizkavēties.
  • Daudzums:
  • Ielikt grozā
  • Piegādes laiks - 4-6 nedēļas
  • Pievienot vēlmju sarakstam
Computability and Complexity Theory 2nd ed. 2011Palielināt
  • Formāts: Hardback, 300 pages, height x width: 235x155 mm, weight: 641 g, XVI, 300 p., 1 Hardback
  • Sērija : Texts in Computer Science
  • Izdošanas datums: 09-Dec-2011
  • Izdevniecība: Springer-Verlag New York Inc.
  • ISBN-10: 1461406811
  • ISBN-13: 9781461406815
Citas grāmatas par šo tēmu:
Permanent link: https://www.kriso.lv/db/9781461406815.html
Keywords:
This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations.  Subsequent chapters move from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability focus on the limitations of computability and the distinctions between feasible and intractable.  Substantial new content in this edition includes:





a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of KarpLipton. a chapter studying properties of the fundamental probabilistic complexity classes a study of the alternating Turing machine and uniform circuit classes. an introduction of counting classes, proving the famous results of Valiant and Vazirani and of Toda a thorough treatment of the proof that IP is identical to PSPACE

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 andpractical learning tool.

 

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 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

Recenzijas

From the reviews:



"The difference between this new introductory graduate textbook in theoretical computer science and other texts is that the authors have chosen to concentrate on computability theory and computational complexity theory. They motivate this focus by pointing out that most students have been introduced to the theory of automata and formal languages as undergraduates. The topics are treated in depth and in full formal detail. Explicit homework assignments are tightly integrated into the exposition of the material." --Computing Reviews



"This book is intended for use in a modern graduate course in the theory of computing. Mainly all old classical complexity results as well as a relatively recent result that space-bounded classes are closed under complements are included into the book. The textbook is self-contained. A list of useful homework problems is appended to each chapter. The book is well written and is recommended to students as well as specialists in theoretical computer science." (Anatoly V. Anisimov, Zentralblatt MATH, Vol. 1033 (8), 2004)



"This book is a solid textbook suited for one- or two-semester graduate courses on the theory of computing. The authors are two leading researchers in the field of theoretical computer sciences, most notably complexity theory. This textbook 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 this book an essential and practical learning tool." (André Grosse, The Computer Journal, Vol. 45 (4), 2002)

1 Preliminaries
1(22)
1.1 Words and Languages
1(1)
1.2 K-adic Representation
2(1)
1.3 Partial Functions
3(1)
1.4 Graphs
4(1)
1.5 Propositional Logic
5(3)
1.5.1 Boolean Functions
7(1)
1.6 Cardinality
8(2)
1.6.1 Ordered Sets
10(1)
1.7 Elementary Algebra
10(13)
1.7.1 Rings and Fields
10(5)
1.7.2 Groups
15(2)
1.7.3 Number Theory
17(6)
2 Introduction to Computability
23(18)
2.1 Turing Machines
24(2)
2.2 Turing Machine Concepts
26(2)
2.3 Variations of Turing Machines
28(7)
2.3.1 Multitape Turing Machines
29(3)
2.3.2 Nondeterministic Turing Machines
32(3)
2.4 Church's Thesis
35(1)
2.5 RAMs
36(5)
2.5.1 Turing Machines for RAMS
40(1)
3 Undecidability
41(34)
3.1 Decision Problems
41(1)
3.2 Undecidable Problems
42(3)
3.3 Pairing Functions
45(2)
3.4 Computably Enumerable Sets
47(3)
3.5 Halting Problem, Reductions, and Complete Sets
50(3)
3.5.1 Complete Problems
52(1)
3.6 S-m-n Theorem
53(3)
3.7 Recursion Theorem
56(2)
3.8 Rice's Theorem
58(2)
3.9 Turing Reductions and Oracle Turing Machines
60(7)
3.10 Recursion Theorem: Continued
67(4)
3.11 References
71(1)
3.12 Additional Homework Problems
71(4)
4 Introduction to Complexity Theory
75(6)
4.1 Complexity Classes and Complexity Measures
76(3)
4.1.1 Computing Functions
79(1)
4.2 Prerequisites
79(2)
5 Basic Results of Complexity Theory
81(42)
5.1 Linear Compression and Speedup
82(7)
5.2 Constructible Functions
89(4)
5.2.1 Simultaneous Simulation
90(3)
5.3 Tape Reduction
93(6)
5.4 Inclusion Relationships
99(10)
5.4.1 Relations Between the Standard Classes
107(2)
5.5 Separation Results
109(4)
5.6 Translation Techniques and Padding
113(4)
5.6.1 Tally Languages
116(1)
5.7 Relations Between the Standard Classes: Continued
117(5)
5.7.1 Complements of Complexity Classes: The Immerman-Szelepcsenyi Theorem
118(4)
5.8 Additional Homework Problems
122(1)
6 Nondeterminism and NP-Completeness
123(22)
6.1 Characterizing NP
124(1)
6.2 The Class P
125(2)
6.3 Enumerations
127(2)
6.4 NP-Completeness
129(2)
6.5 The Cook-Levin Theorem
131(5)
6.6 More NP-Complete Problems
136(6)
6.6.1 The Diagonal Set Is NP-Complete
137(1)
6.6.2 Some Natural NP-Complete Problems
138(4)
6.7 Additional Homework Problems
142(3)
7 Relative Computability
145(36)
7.1 NP-Hardness
147(3)
7.2 Search Problems
150(3)
7.3 The Structure of NP
153(8)
7.3.1 Composite Number and Graph Isomorphism
157(3)
7.3.2 Reflection
160(1)
7.4 The Polynomial Hierarchy
161(8)
7.5 Complete Problems for Other Complexity Classes
169(9)
7.5.1 PSPACE
169(4)
7.5.2 Exponential Time
173(1)
7.5.3 Polynomial Time and Logarithmic Space
174(4)
7.5.4 A Note on Provably Intractable Problems
178(1)
7.6 Additional Homework Problems
178(3)
8 Nonuniform Complexity
181(20)
8.1 Polynomial Size Families of Circuits
184(7)
8.1.1 An Encoding of Circuits
187(1)
8.1.2 Advice Classes
188(3)
8.2 The Low and High Hierarchies
191(10)
9 Parallelism
201(24)
9.1 Alternating Turing Machines
201(8)
9.2 Uniform Families of Circuits
209(4)
9.3 Highly Parallelizable Problems
213(3)
9.4 Uniformity Conditions
216(3)
9.5 Alternating Turing Machines and Uniform Families of Circuits
219(6)
10 Probabilistic Complexity Classes
225(22)
10.1 The Class PP
225(4)
10.2 The Class RP
229(2)
10.2.1 The Class ZPP
230(1)
10.3 The Class BPP
231(6)
10.4 Randomly Chosen Hash Functions
237(5)
10.4.1 Operators
239(3)
10.5 The Graph Isomorphism Problem
242(4)
10.6 Additional Homework Problems
246(1)
11 Introduction to Counting Classes
247(14)
11.1 Unique Satisfiability
249(4)
11.2 Toda's Theorem
253(7)
11.2.1 Results on BPP and P
253(4)
11.2.2 The First Part of Toda's Theorem
257(1)
11.2.3 The Second Part of Toda's Theorem
257(3)
11.3 Additional Homework Problems
260(1)
12 Interactive Proof Systems
261(22)
12.1 The Formal Model
261(2)
12.2 The Graph Non-Isomorphism Problem
263(2)
12.3 Arthur-Merlin Games
265(2)
12.4 IP Is Included in PSPACE
267(3)
12.5 PSPACE Is Included in IP
270(12)
12.5.1 The Language ESAT
270(4)
12.5.2 True Quantified Boolean Formulas
274(1)
12.5.3 The Proof
275(7)
12.6 Additional Homework Problems
282(1)
References 283(6)
Author Index 289(2)
Subject Index 291