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ự động hoá
• Technologies
• Systems Engineering
• robotic
• mechanical
• anatomy
• Network security technologies
• Ebook Network security technologies
• Security in network design
• Basic confidentiality technologies
• Basic authentication technologies
• Basic message integrity technologies
• Solar assisted technologies for cooling and air conditioning
• Solar assisted technologies
• Solar assisted technologies currently
• Solar thermal and solar photovoltaic
• The installed solar assisted technologies currently
• Emerging technologies in surgery
• Emerging technologies
• Organizing surgical simulation centers
• Disruptive technologies
• Telecom Services
• Wireless Technologies
• Fiber—Optical Technologies
• IP Technologies
• Security and Surveillance
• Location Technologies
• Agilent Technologies 8648A B C D Signal Generator
• Service Guide Agilent Technologies 8648A B C D
• Operation Agilent Technologies 8648A B C D
• Motherboard Audio Path
• HF Power Level Accuracy
• LF Output Level
• Advanced learning technologies
• Performance technologies
• Performance management
• Open education
• Technology standardization
• Economic and psychological profile
• Redgram technologies
• Farm university technologies
• Application of technologies
• Market price
• Labour scarcity
• Mango growers
• Recommended technologies in mango
• Recommended technologies
• Adoption of recommended technologies
• Production of mango
• Production technology
• Search of technologies
• Identification of technologies
• Selection of technologies
• Technological innovation
• Higher education
• South Africa
• Learning technologies
• Agroclimatic zone IV
• Adoption of improved maize production technologies
• Improved maize production technologies
• Farmers of agro climatic zone IV
• Maize production technologies
• Lecture Java technologies
• Bài giảng công nghệ Java
• Công nghệ Java
• Content of lesson Java technologies
• Tools of Java technologies
• Advanced Automotive Technologies
• advanced vehicles
• technical potential and cost
• technology price estimates
• electric drivetain technologies
• nature of the technology
• The Grid
• Core Technologies
• detail OGSA
• SR 168 Portlets
• Home Systems
• Semantic Technologies
• Healthcare Technologies
• Home Gateway
• Place Framework
• Related Technologies
• Tumor Markers
• New Technologies
• potential measurements
• Magnetic resonance
• microwave imaging
• Energy Supply
• Energy Technologies
• Environmental Technologies
• Coal Mining
• Nuclear Power
• Regulatory Framework
• Access Techniques
• CDMA Technologies
• CDMA2000 1X
• 1X EV DO
• Access Technology
• UTRA Technologies
• Available Technologies
• Reducing Greenhouse Gas Emissions
• Pulp and Paper Manufacturing Industry
• New health technologies
• Managing access
• The past and potential future impact
• Access and value in pharmaceuticals
• New health technology
• Business intelligence
• Lecture Business intelligence
• Information integration
• Technologies enabling insights
• Business analytics
• Data mining
• Technologies enabling presentation
• Decision making
• Tactical decisions
• Strategic decisions
• Web technologies
• Web programming
• Web applications
• Computer programming
• Web development technologies
• Categories of web applications
• Characteristics of web applications
• Web project management
• Web application development process
• Requirement engineering
• Modeling web applications