在精确的4SAT（EXACT 4SAT）问题中，输入为一组子句，每个字句都是恰好4个文字的析取，且每个变量最多在每个子句中出现一次。目标是求它的满足赋值——如果该赋值存在。证明精确的4SAT是NP-完全问题。
首先很明显，EXACT 4SAT属于NP。现在通过将3SAT规约到EXACT 4SAT来证明后者的NP完全性。
对于任意一个3SAT实例，如果其中某个子句中包含了同一个文字多次，那么可以缩减为一次，如果同时包含了某个变量的肯定及否定，那么可以将这个变量去掉。然后，可以再在每个字句中可以添加一些哑变量（即没用的的辅助变量），这样就可以将每个子句所包含的文字数目扩充到四个。至此，即已将该3SAT实例转化成了一个EXACT 4SAT问题。
一、题目 在精确的4SAT（EXACT 4SAT）问题中，输入为一组子句，每个字句都是恰好4个文字的析取，且每个变...
算法《算法概论》《算法设计与分析基础》 Anany Levitin《算法引论》Udi Manber《算法导论》《什...
题目： 2.14 给定一个含有n个元素的数组，注意到数组中的某些元素是重复的，即这些元素在数组中出现不止一次。给出...
1.监督学习和无监督学习： 监督学习（supervised learning）： 输入数据有特征值和标签值，利...
1.算法定义 算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法 2.算法的五个特性 确定性：无二...
前言 算法与数据结构是计算机科学中的核心内容，算法是研究解决问题的方法，而数据结构则是设计一种更好的组织和使用数据...
1.概念 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 2...
数据结构目录 1.概念 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多...
现实生活中有很大一类问题可以用简洁明了的图论语言来描述，可以转化为图论问题。 相关定义 图可以表示为G=(V, E...
a. 令图G 为一个环，环上的顶点数等于图 H 的顶点数。那么若G 是 H 的同构子图，则说明 H 存在 Rudr...
本文标题：算法概论 8.8证明题
本文链接：https://www.haomeiwen.com/subject/ynkqhxtx.html
网友评论