| MAX-k-SAT的PTAS归约等价性 |
| |
| 引用本文： | 许道云,秦永彬.MAX-k-SAT的PTAS归约等价性[J].计算机科学与探索,2009,3(6):641-648. |
| |
| 作者姓名： | 许道云 秦永彬 |
| |
| 作者单位： | 贵州大学计算机科学系,贵阳,550025 |
| |
| 摘 要： | 通过构造适当的极小不可满足公式,利用子句拼接技术,引入了一个一般化的从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等价 |
| 修稿时间： | |
Equivalence of PTAS Reduction for MAX-k-SAT |
| |
| XU Daoyun,QIN Yongbin.Equivalence of PTAS Reduction for MAX-k-SAT[J].Journal of Frontier of Computer Science and Technology,2009,3(6):641-648. |
| |
| Authors: | XU Daoyun QIN Yongbin |
| |
| Affiliation: | Department of Computer Science， Guizhou University， Guiyang 550025， China |
| |
| 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. |
| |
| Keywords: | minimal unsatisfiable formula reduction MAX-k-SAT problem PTAS equivalence |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学与探索》浏览原始摘要信息 |
|
点击此处可从《计算机科学与探索》下载全文 |
|
