COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Comple...
(为.djvu文件,可用WinDjView 打开) COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness by Michael R. Garey & David S. Johnson Content 1 Computers, Complexity, and Intractability 1 1.1 Introduction 1 1.2 Problems, Algorithms, and Complexity 4 1.3 Polynomial Time Algorithms and Intractable Problems 6 1.4 Provably Intractable Problems 11 1.5 NP-Complete Problems 13 1.6 An Outline of the Book 14 2 The Theory of NP-Completeness 17 2.1 Decision Problems, Languages, and Encoding Schemes 18 2.2 Deterministic Turing Machines and the Class P 23 2.3 Nondeterministic Computation and the Class NP 27 2.4 The Relationship Between P and NP 32 2.5 Polynomial Transformations and NP-Completeness 34 2.6 Cook's Theorem 38 3 Proving NP-Completeness Results 45 3.1 Six Basic NP-Complete Problems 46 3.1.1 3-SATISF1ABIL1TY 48 3.1.2 3-DIMENS10NAL MATCHING 50 3.1.3 VERTEX COVER and CLIQUE 53 3.1.4 HAMILTONIAN CIRCUIT 56 3.1.5 PARTITION 60 3.2 Some Techniques for Proving NP-Completeness 63 3.2.1 Restriction 63 3.2.2 Local Replacement 66 3.2.3 Component Design 72 3.3 Some Suggested Exercises 74 4 Using NP-Completeness to Analyze Problems 77 4.1 Analyzing Subproblems 80 4.2 Number Problems and Strong NP-Completeness 90 4.2.1 Some Additional Definitions 92 4.2.2 Proving Strong NP-Completeness Results 95 4.3 Time Complexity as a Function of Natural Parameters .... 106 5 NP-Hardness 109 5.1 Turing Reducibility and NP-Hard Problems 109 5.2 A Terminological History 118 6 Coping with NP-Complete Problems 121 6.1 Performance Guarantees for Approximation Algorithms ...123 6.2 Applying NP-Completeness to Approximation Problems ...137 6.3 Performance Guarantees and Behavior "In Practice" 148 7 Beyond NP-Completeness 153 7.1 The Structure of NP 154 7.2 The Polynomial Hierarchy 161 7.3 The Complexity of Enumeration Problems 167 7.4 Polynomial Space Completeness 170 7.5 Logarithmic Space 177 7.6 Proofs of Intractability and P vs. NP 181
- 粉丝: 0
- 资源: 1
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于SpringBoot Mybatis-Plus TypeScript的微服务多租户SaaS管理快速开发框架 .zip
- 论文复现:QA-GNN: Reasoning with Language Models and Knowledge
- ipp(intel-oneAPI)下载地址.txt
- 基于spring-boot dubbox搭建的java分布式系统的前端管理.zip
- VLC+Qt demoVLC+Qt demo
- 海彪&龙梅子 - 寂寞的人伤心的歌 (DJ版) [mqms2].ogg
- 530springboot + vue 旅游管理系统.zip(可运行源码+数据库文件+文档)
- 基于SpringBoot + Thymeleaf + Layui + Apache Shiro 的后台管理系统 .zip
- 表1:长江大学文理学院课外学分申请表.et
- base.apk
- 1
- 2
- 3
- 4
前往页