TAILIEUCHUNG - Complexity Theory Johan H˚ astad Department of Numerical Analysis and Computing Science Royal Institute of Technology

The word "technology" can also be used to refer to a collection of techniques. In this context, it is the current state of humanity's knowledge of how to combine resources to produce desired products, to solve problems, fulfill needs, or satisfy wants; it includes technical methods, skills, processes, techniques, tools and raw materials. When combined with another term, such as "medical technology" or "space technology", it refers to the state of the respective field's knowledge and tools. "State-of-the-art technology" refers to the high technology available to humanity in any field | Complexity Theory Johan Hastad Department of Numerical Analysis and Computing Science Royal Institute of Technology S-100 44 Stockholm SWEDEN johanh@ May 13 2009 1 Contents 1 Preface 4 2 Recursive Functions 5 Primitive Recursive Functions. 6 Partial recursive functions. 10 Turing Machines. 11 Church s thesis. 15 Functions sets and languages. 16 Recursively enumerable sets. 16 Some facts about recursively enumerable sets. 19 Godel s incompleteness theorem. 26 Exercises . 27 Answers to exercises. 28 3 Efficient computation hierarchy theorems. 32 Basic Definitions. 32 Hierarchy theorems. 33 4 The complexity classes L P and PSPACE. 39 Is the definition of P model dependent . 40 Examples of members in the complexity classes. 48 5 Nondeterministic computation 56 Nondeterministic Turing machines. 56 6 Relations among complexity classes 64 Nondeterministic space vs. deterministic time. 64 Nondeterministic time vs. deterministic space. 65 Deterministic space vs. nondeterministic space. 66 7 Complete problems 69 NP-complete problems. 69 PSPACE-complete problems. 78 P-complete problems. 82 AL-complete problems. 85 8 Constructing more complexity-classes 86 2 9 Probabilistic computation 89 Relations to other complexity classes. 94 10 Pseudorandom number generators 95 11 Parallel computation 106 The circuit model of NC. 108 Parallel time vs sequential space .112 12 Relativized computation 116 13 Interactive proofs 123

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.