- 1、本文档共15页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Reducibility among Combinatorial Problems问题之间的规约证明
By 果果
证明格式
证明Π∈NP
1. 最优性问题转为判定性问题
2. 构造非确定多项式时间算法
a) 猜想…… (多项式时间复杂度)
b) 检查…… (多项式时间复杂度)
c) 若是,回答“yes”,否则回答“no”
多项式时间变换 ≤
1. 对 的每个实例I (列出所有参数和限制)
1
2. 构造 对应实例f(I) (计算参数,检查限制)
2
3. 证明f 是多项式时间算法
4. 证明I 是“yes”实例当且仅当f(I)是“yes”实例
证明Π 是NP 完全的
1. 证明Π∈NP
2. 找到已知的NP 完全问题Π’,证明Π’≤ Π
1. SAT ∝ 0-1 整数规划
问题回顾:
SAT: 输入析取范式 , , … , , 是否有赋值使得它们都为真
1 2
0-1 整数规划: 输入矩阵C 和列向量d,是否有0-1 组成的列向量X 使得CX = d
输入对应:
SAT 中的每个析取范式 , , … , 是由符号集{ , , … , ; ̅̅̅, ̅̅̅, … , ̅̅̅}的部分
1 2 1 2 1 2
组成的。
构造相应的0-1 整数规划问题的输入矩阵C 和列向量d
1, ∈
= { = 1 – ( 中补变量的个数)
−1, ̅ ∈
0, ℎ
= +
输入多项式时间转化:
转化的步骤需要构造矩阵C,构造过程需要的复杂度为矩阵的元素数和列向量的元素数,
即为O(np) ,是多项式的。
输出对应:
若SAT 问题中存在赋值使得 , , … , 都为真,将这个赋值作为0-1 整数规划问题的
1 2
列向量解 X ,则有 CX 所得的列向量的分量有 ’ = ∑ ∗ ≧ ,构造非负的松弛变
=0
量 ,使得∑ ∗ = + ,则每个 SAT 的解对应上面的变换可以得到CX = d 的
=0
解。
若0-1 整数规划问题中有解X 使得CX = d,则该X 对应可以使得 , , … , 均为真的
1 2
赋值。考虑任意 , 为0 当且仅当所有 ∈ 取 = 0,所有 ̅ ∈ 取 = 1,则
可知∑ ∗ = – 1,
您可能关注的文档
- PKPM V2.1改进要点.pdf
- PKS系统FANOUT功能块.pdf
- PLC-可编程逻辑控制器2.pdf
- plaxis V8.5参考手册.pdf
- PLC初学教材.pdf
- PKPM2010(V2.2_2015.6.26)改进说明.pdf
- PLC电气控制与组态设计2014最新版 第一章.pdf
- PLC编程及应用第2章PLC结构和工作原理.pdf
- PLI中文说明书.pdf
- PLE-SDT说明书.pdf
- 2024高考物理一轮复习规范演练7共点力的平衡含解析新人教版.doc
- 高中语文第5课苏轼词两首学案3新人教版必修4.doc
- 2024_2025学年高中英语课时分层作业9Unit3LifeinthefutureSectionⅢⅣ含解析新人教版必修5.doc
- 2024_2025学年新教材高中英语模块素养检测含解析译林版必修第一册.doc
- 2024_2025学年新教材高中英语单元综合检测5含解析外研版选择性必修第一册.doc
- 2024高考政治一轮复习第1单元生活与消费第三课多彩的消费练习含解析新人教版必修1.doc
- 2024_2025学年新教材高中英语WELCOMEUNITSectionⅡReadingandThi.doc
- 2024_2025学年高中历史专题九当今世界政治格局的多极化趋势测评含解析人民版必修1.docx
- 2024高考生物一轮复习第9单元生物与环境第29讲生态系统的结构和功能教案.docx
- 2024_2025学年新教材高中英语UNIT5LANGUAGESAROUNDTHEWORLDSect.doc
文档评论(0)