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

Equivalence of PTAS Reduction for MAX-k-SAT

作　　者：许道云[1] 秦永彬[1] 

机构地区：[1]贵州大学计算机科学系,贵阳550025

出　　处：《计算机科学与探索》2009年第6期641-648,共8页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金~~

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]