【问题描述】
若子集族F是有限集X的一个的集合覆盖,则F中覆盖X的互不相交的子集族T称为<X, F>的精确覆盖。已知3-SAT是NP完全的,证明精确覆盖问题(<X, F>是否有精确覆盖)是NP完全的。
【个人思路】
问题可以简化为:已知3-SAT是NP完全的,证明精准覆盖问题也是NP完全的。首先要证明精准覆盖问题是NP的,接下来可以用规约:3-SAT->精准覆盖来证明精准覆盖的NP完全性。用规约证明的第一步是证明3-SAT问题的输入可以映射到精准覆盖,第二步是证明精准覆盖的输出可以映射到3-SAT问题。
![](https://profile-avatar.csdnimg.cn/00ba1708f26e40c083260b0e2c93e9be_wistain.jpg!4)
已知3-SAT是NP完全的,如何规约证明精准覆盖问题的NP完全性?(关键词-精确覆盖)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
0条回答 默认 最新
悬赏问题
- ¥200 csgo2的viewmatrix值是否还有别的获取方式
- ¥15 Stable Diffusion,用Ebsynth utility在视频选帧图重绘,第一步报错,蒙版和帧图没法生成,怎么处理啊
- ¥15 请把下列每一行代码完整地读懂并注释出来
- ¥15 pycharm运行main文件,显示没有conda环境
- ¥15 易优eyoucms关于二级栏目调用的问题
- ¥15 寻找公式识别开发,自动识别整页文档、图像公式的软件
- ¥15 为什么eclipse不能再下载了?
- ¥15 编辑cmake lists 明明写了project项目名,但是还是报错怎么回事
- ¥15 关于#计算机视觉#的问题:求一份高质量桥梁多病害数据集
- ¥15 特定网页无法访问,已排除网页问题