Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
A computer is a general purpose device that can be programmed to carry out a finite set of arithmetic or logical operations. Since a sequence of operations can be readily changed, the computer can solve more than one kind of problem. | Complexity Theory Johan Hastad Department of Numerical Analysis and Computing Science Royal Institute of Technology S-100 44 Stockholm SWEDEN johanh@nada.kth.se May 13 2009 1 Contents 1 Preface 4 2 Recursive Functions 5 2.1 Primitive Recursive Functions. 6 2.2 Partial recursive functions. 10 2.3 Turing Machines. 11 2.4 Church s thesis. 15 2.5 Functions sets and languages. 16 2.6 Recursively enumerable sets. 16 2.7 Some facts about recursively enumerable sets. 19 2.8 Godel s incompleteness theorem. 26 2.9 Exercises . 27 2.10 Answers to exercises. 28 3 Efficient computation hierarchy theorems. 32 3.1 Basic Definitions. 32 3.2 Hierarchy theorems. 33 4 The complexity classes L P and PSPACE. 39 4.1 Is the definition of P model dependent . 40 4.2 Examples of members in the complexity classes. 48 5 Nondeterministic computation 56 5.1 Nondeterministic Turing machines. 56 6 Relations among complexity classes 64 6.1 Nondeterministic space vs. deterministic time. 64 6.2 Nondeterministic time vs. deterministic space. 65 6.3 Deterministic space vs. nondeterministic space. 66 7 Complete problems 69 7.1 NP-complete problems. 69 7.2 PSPACE-complete problems. 78 7.3 P-complete problems. 82 7.4 AL-complete problems. 85 8 Constructing more complexity-classes 86 2 9 Probabilistic computation 89 9.1 Relations to other complexity classes. 94 10 Pseudorandom number generators 95 11 Parallel computation 106 11.1 The circuit model of computation.106 11.2 NC. 108 11.3 Parallel time vs sequential space .112 12 Relativized computation 116 13 Interactive proofs 123