NPC理论导引

文档类型

价格(积分)

购买连接

试读

PDF格式

1、本站所有的书默认都是PDF格式，该格式图书只能阅读和打印，不能再次编辑。

2、除分上下册或者多册的情况下，一般PDF页数一定要大于标注页数才建议下单购买。【本资源233 ≥223页】

1、所有的电子图书为PDF格式，支持电脑、手机、平板等各类电子设备阅读；可以任意拷贝文件到不同的阅读设备里进行阅读。

2、电子图书在提交订单后一般半小时内处理完成,最晚48小时内处理完成。(非工作日购买会延迟)

3、所有的电子图书都是原书直接扫描方式制作而成。

目录 1

第1章　基础概念 1

§1.1　问题的难易性，复杂度的直观概念 1

§1.2　确定型图灵机与P类，基于图灵机的复杂度概念 14

§1.3　非确定型计算与NP类，P与NP的关系 31

§1.4　多项式变换、NPC类与Cook定理 40

第2章　证明问题属于NPC类的方法 55

§2.1　基本的和常见的NPC问题 55

§2.2　关于NPC的证明方法 81

第3章　P与NPC的分界，证明问题属于P类的方法 96

§3.1　P类问题与NPC类问题的分界 96

§3.2　证明问题属于P类的例 98

第4章　对付NPC问题的办法 124

§4.1　近似算法 124

§4.2　概率算法 181

第5章　NP类的结构及进一步的知识 203

§5.1　NP的结构 203

§5.2　CO-NP类 204

§5.3　伪多项式时间算法与强NPC 207

§5.4　PSPACE完全类 212

§5.5　相对化计算的概念 214

§5.6 ＃P完全性简述 216

参考文献 221