3-SAT归约到独立集问题
3-SAT归约到独立集问题
【3-SAT ≤p\leq_p≤p 独立集】
要证明3-SAT问题可以归约到独立集，就需要证明，有一个关于独立集的黑盒子，通过解3-SAT实例，能够解3-SAT问题。
图4为从3-SAT到独立集归约的一个实例。
图4 从3-SAT到独立集的归约
对于一个子句来说，只要有一项的值为真，则整个子句的值为真。
则，根据子句可以这样构造图：对于每一个子句，创建三个点，将三个点连接成三角形（如上图）。若存在两个子句中有x1x_1x1和x‾1\overline x_1x1,则在这两个节点之间添加一条边（称为冲突变，即这两边不能同时被选到）。
则，存在一个真值赋值，当且仅
文件下载
评论信息
其他资源
- BP神经网络实现气温学习和预测代码及代码分析(python+tensorflow).zip
- 组态王彻底卸载及重新安装
- 空间计量经济学－从横截面数据到空间面板（中文版）－埃尔霍斯特.pdf
- mms61850源码，电力客户端服务端通讯mmslite-6.0000
- 飞行器系统辩识学
- 计算电磁学（2002年第1版 王秉中 科学出版社-）
- 精通DirectX.3D图形与动画程序设计.pdf
- The scientist and engineer's guide to digital signal processing.pdf
- 说话人识别代码
- 商品销售管理系统源码和附加数据库
- 《瓦尔登湖》导学案.docx
- 123个微信小程序源码打包 小程序教程.txt
- jdk-8u11-windows-x64.exe
- .net版本简单线程调用源码__0525.rar
- 晓风彩票网站源码开源版
- unity插件 build report tool
- fir滤波器 quartus2
- deepin-qq+crossover+crossover-helper
- 在VC 6.0的opencv环境下视频显示与捕捉
- C#仓库管理系统
- 用友软件小工具
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明