TAILIEUCHUNG - Complexity TheoryJohan H˚ astad Department of Numerical Analysis and Computing Science Royal Institute of Technology S-100

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

• Kỹ thuật lập trình
• Computer
• Machine code
• Programming language
• Program design
• Components
• mainboard
• computer assembly
• computer hardware
• assembly engineering
• computer engineering
• computer skills
• hardware architectures
• computer basics
• computer architecture computer
• computer components
• Computer Literacy
• Lecture Computer literacy
• Computer science
• Introduction to computers
• Computer applications
• Computer Networks
• Computer Ethics
• computer security
• network security
• data security
• a virus
• computer protection
• computer tips
• document of Pro drupal 7
• Transferring images
• Windows XP Hacks & Mods for Dummies
• Converged Network Security for Dummies
• hardware architecture
• computer repair
• computer installation
• computer architecture
• Converged Network Security
• computer Scientist
• computer document
• ebook computer
• computer specific study
• Engineering Department
• Computer Scienc
• Feaculty of Computer Science
• remove the median element
• computer history
• computer manufacturing technology
• personal computer history
• Computer concepts
• Computer concepts in action
• Lecture Computer concepts in action
• Computer advertisements
• Create a spreadsheet
• Central Processing Unit
• Operating system software
• Operating system
• Folder properties
• Storage devices