Reducibility-among-Combinatorial-Problems问题之间的规约证明

Karp

需积分: 24 142 浏览量 2018-05-27 19:53:51 上传评论收藏 800KB PDF 举报

资源推荐

资源详情

资源评论

果果

证明格式

证明 

1. 最优性问题转为判定性问题

2. 构造非确定多项式时间算法

a) 猜想（多项式时间复杂度）

b) 检查（多项式时间复杂度）

c) 若是，回答，否则回答

多项式时间变换











1. 对



的每个实例 （列出所有参数和限制）

2. 构造



对应实例 󰇛󰇜（计算参数，检查限制）

3. 证明 是多项式时间算法

4. 证明 是实例当且仅当 󰇛󰇜是实例

证明 是 完全的

1. 证明 

2. 找到已知的  完全问题 证明 





1.  整数规划

问题回顾：

输入析取范式











是否有赋值使得它们都为真

 整数规划输入矩阵 和列向量 ，是否有  组成的列向量 使得 

输入对应：

中的每个析取范式











是由符号集󰇝





























󰇞的部分

组成的。

 构造相应的  整数规划问题的输入矩阵  和列向量 





󰇱



，























󰇛



中补变量的个数󰇜













输入多项式时间转化：

转化的步骤需要构造矩阵 ，构造过程需要的复杂度为矩阵的元素数和列向量的元素数，

即为 󰇛󰇜，是多项式的。

输出对应：

若 问题中存在赋值使得











都为真，将这个赋值作为  整数规划问题的

列向量解 ，则有 所得的列向量的分量有













 







构造非负的松弛变

量



使得









 







 



则每个 的解对应上面的变换可以得到 的

解。

若 整数规划问题中有解 使得 ，则该  对应可以使得











均为真的

赋值。考虑任意







为 当且仅当所有







取



，所有







取



，则

可知









 







，即若



不成立 对应的分量不可能等于



，与 矛

盾。故











均为真。

果果

2. 

问题回顾：

：输入一个图 和一个正整数 ，判断图 中是否有大小为 的团

输入对应：

图中顶点集为：

󰇝是



中出现的符号󰇞

边集为：

󰇝󰇝󰇞且 



󰇞



输入多项式时间转化：

转化后所得到的顶点数，至多有  个，为析取范式中可能出现的符号数。

对没有个顶点，可能与之相连的顶点，符号可能的取值有󰇛󰇜种，可

能的取值最多有󰇛󰇜种，故边总共不会超过󰇛󰇜󰇛󰇜󰇛󰇜条。

故转化的整体时间是 󰇛







󰇜的。

输出对应：

分析输入对应的性质，图中的每一个顶点其实表达的是一种状态：即符号  可以使析取

式取真。

若 问题中存在赋值使得所有的析取范式都为真，设赋值序列为󰇝











󰇞，对

每一个



，都可以在赋值序列中找到使得



对应为真的符号



，这也就对应了图 中的

一个点



，则我们可以在图 中找到 个点



，



，，



这 

个点的第二个分量从 到 显然不相同，而由于这 个点的第一个符号是对应了同一

个赋值序列中使析取式为真的赋值，故不会出现两个符号互为补变量的情况，故这 个

点之间彼此都有边，即这  个点构成了一个  大团。

若 问题解，即图中存在  个点彼此之间都有连线。根据构造输入时边的构造规

则可知，这  个点第二个分量都不相同，所以每一个顶点可以对应一个符号的取值使得

对应的析取式为真，同时这 个点的第一个分量互相不是补变量，即这些符号能同时取

真，所以将这 个点对应的符号都取真，便可以对应 问题的一组使得所有析取式

为真的输入。

3. 

问题回顾：

：对集族󰇝



󰇞和一个正整数 ，在集族󰇝



󰇞是否存在  个互不相交的集合。

输入对应：

设原图中的节点为 󰇝󰇞，每一个节点 对应  问题中一个输入的

集合



󰇝󰇝󰇞󰇝󰇞󰇞，（ 是原图的边集）。取 。

输入多项式时间转化：

原问题的节点的个数为 问题的集合的个数，集合中元素的和为原图的补

图中边的条数，所以元素个数至多为 󰇛󰇜所以构造相应的输入需要的复杂度是

󰇛



󰇜的。

输出对应：

如果 问题中存在一个 大团，则将这些顶点对应的集合也构成 

问题一个满足要求的实例，若存在两个集合使得







不为空，则







中的元素仅能为

󰇝󰇞，但若󰇝󰇞



，则表示󰇝󰇞，这与 和 是原图 大团中的两个顶点󰇝󰇞矛

果果

盾。所以不存在







不为空，所以选出来的这  个集合是满足要求的。

如果 问题中存在 个集合彼此之间没有交集，则这些集合对应的顶点在

原图中构成一个 大团。设 和 是根据  问题的实例选出的两个顶点，若

和  之间没有边，则󰇝󰇞



且󰇝󰇞



，这与







为空集矛盾，所以选出来的这 个顶

点，任意两点之间都有边。所以这 个点是满足要求的实例。

4. 

问题回顾：

：输入一张图 和一个正整数 ，是否存在一个点集 使得，且

图 中的每个边都在  中找到与之相关联的点。

输入对应：

在  问题中取 为  中图 的补图，取 

输入多项式时间转化：

图 中顶点的个数为原图的顶点数 ，边的条数为 󰇛󰇜󰇛为原图中边的条数󰇜所

以转化是多项式时间的

输出对应：

如果  问题中存在一个满足要求的实例。即图 中存在一个 阶完全子图 ，设

这个子图对应的顶点的集合为 。则 能构成 问题中的点覆盖。若

在图 中存在一条边 与 中的点不相关，则 连接了 中的两个点，设为 ，

即󰇝󰇞属于 的补图中，即󰇝󰇞，与 为 阶完全子图矛盾。所以 中任意一条边

都与  中的点相关，所以  构成了 中的一个点覆盖。且。

如果 问题中存在一个满足要求的点覆盖 。则在图 中任意两点 和 

（），和 之间没有边，否则与 是图 的点覆盖矛盾。又因为图 是图 的补

图，所以任意两点 和 属于󰇛󰇜，在图 中 和 中有边，所以󰇛󰇜构成图 中的

一个完全子图，这个完全子图的阶数是大于等于 的，所以图  中存在 阶完全子图。

5. 

问题回顾：

：给定有限个集合组成的集族󰇝



󰇞，和一个正整数 。判断是否存在󰇝



󰇞

的一个子集󰇝



󰇞󰇝



󰇞，使得󰇝



󰇞󰇝



󰇞，且󰇝



󰇞

输入对应：

设󰇝󰇞为原图 中的顶点集，则取集合



为  图 中与顶点 相关的

边组成的集合作为 问题的输入。且去 。

输入多项式时间转化：

图 中有 个顶点，所以 问题中有 个集合，这些集合内的元素为图

中的边。而图 中的边同时与两个点相关，所以会出现在两个集合中，所以所有集合

的元素的个数和为 ，所以输入转化的复杂度为 󰇛󰇜

输出对应：

若 问题中存在满足条件的点覆盖集 ，，则与 中的顶点相关的集

合作为



的元素。则图 中任意一条边 都能在 中找到与之相关的点 ，则 



，所

以 󰇝



󰇞，所以󰇝



󰇞󰇝



󰇞原图的边集，且󰇝



󰇞，所以 

中存在符合条件的󰇝



󰇞。

剩余14页未读，继续阅读

评论收藏

内容反馈

weixin_40485865

粉丝: 0
资源: 1

Reducibility-among-Combinatorial-Problems问题之间的规约证明

Reducibility Among Combinatorial Problems论文报告

constructive-and-synthetic-reducibility-in-coq

COMPUTERS AND INTRACTABILITY： A Guide to the Theory of NP-Completeness

Solution-Manual-Introduction-to-the-Theory-of-Computation-Sipser

算法导论--Introduction.to.Algorithms

Reflexivity and reducibility of operators related to invariant subspace problem

算法导论-introduction to algrithms 3rd edition

算法导论英文版

算法导论 第三版 英文原版 高清文字版

Recursive Mathematics - Volume 1 Recursive Model Theory

Recursive Mathematics - Volume 1 Recursive Model Theory part2

Tunable reducibility of Brillouin zone and bandgap width in elliptical nanowire arrays

Vector Davinci官方帮助配置使用手册（AutoSAR）.pdf

c++入门，核心，提高讲义笔记

数字图像处理 冈萨雷斯 课后习题

离散数学及其应用 第八版 奇数编号练习答案.pdf

科研伦理与学术规范 期末考试2 （40题）.pdf

最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理.emmx

软件著作权设计说明书模板（含填写说明）.docx

AUTOSAR培训教材.rar

菜菜sklearn课程讲义.rar

“互联网+”大学生创新创业大赛项目计划书

notepad++-7.9下载

HALCON快速入门手册.pdf

最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附带做题技巧/易错点/知识点整理.emmx

LabView 官方教程（全）

SMA_Connector.zip

AUTOSAR官方培训教材.zip

最新资源

算法导论第三版英文原版高清文字版

数字图像处理冈萨雷斯课后习题

离散数学及其应用第八版奇数编号练习答案.pdf

科研伦理与学术规范期末考试2 （40题）.pdf

最值得收藏的考研线性代数全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理.emmx

最值得收藏的考研高等数学全部知识点思维导图整理(张宇, 汤家凤), 附带做题技巧/易错点/知识点整理.emmx