MAX-k-SAT的PTAS归约等价性

• 作者: 秦永彬 许道云
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 极小不可满足公式 归约 MAX-k-SAT问题 PTAS等价
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 学术研究
• 页码范围: 641-648
• 页数: 8页
• 分类号: TP301
• 字数: 7576字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2009.06.009

摘要

通过构造适当的极小不可满足公式,利用子句拼接技术,引入了一个一般化的从k-CNF公式(k≥3)到3-CNF公式之间的归约转换.基于该转换,给出了一个真值指派的转换算法,并证明了MAX-k-SAT与MAX-3-SAT是PTAS归约等价的.因此,对于k,t≥3,MAX-k-SAT与MAX-t-SAT是PTAS归约等价的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	秦永彬	贵州大学计算机科学系	63	213	8.0	10.0