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

doi:10.3778/j.issn.1673-9418.2009.06.009

计算机科学与探索 ›› 2009, Vol. 3 ›› Issue (6): 641-648.DOI: 10.3778/j.issn.1673-9418.2009.06.009

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

许道云+，秦永彬

贵州大学计算机科学系，贵阳 550025

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-11-15 发布日期:2009-11-15
通讯作者: 许道云

Equivalence of PTAS Reduction for MAX-k-SAT

XU Daoyun+， QIN Yongbin

Department of Computer Science， Guizhou University， Guiyang 550025， China

Received:1900-01-01 Revised:1900-01-01 Online:2009-11-15 Published:2009-11-15
Contact: XU Daoyun

摘要/Abstract

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

关键词: 极小不可满足公式, 归约, MAX-k-SAT问题, PTAS等价

Abstract: By constructing proper minimal unsatisfiable formulas and concatenating clauses， a general reduction transformation from k-CNF formulas （k≥3） to 3-CNF formulas is introduced. Based on this transformation， present an algorithm for the transformation of truth assignments， and show that MAX-k-SAT is PTAS （polynomial-time approximation scheme） equivalent to MAX-3-SAT. Thus， MAX-k-SAT is PTAS equivalent to MAX-t-SAT for k， t≥3.

Key words: minimal unsatisfiable formula, reduction, MAX-k-SAT problem, PTAS equivalence

中图分类号:

TP301

许道云+，秦永彬. MAX-k-SAT的PTAS归约等价性[J]. 计算机科学与探索, 2009, 3(6): 641-648.

XU Daoyun+， QIN Yongbin. Equivalence of PTAS Reduction for MAX-k-SAT[J]. Journal of Frontiers of Computer Science and Technology, 2009, 3(6): 641-648.

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

Equivalence of PTAS Reduction for MAX-k-SAT

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics