逼近MAX 3SAT-2问题的难解性(英文)  

Hardness of approximating MAX 3SAT-2

作　　者：陈文彬[1] 

机构地区：[1]广州大学计算机科学与教育软件学院,广东广州510006

出　　处：《广州大学学报（自然科学版）》2012年第2期6-9,共4页Journal of Guangzhou University:Natural Science Edition

摘　　要：证明了逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.首先引进了一种保留近似算法难解性的K-归约的概念;然后给出了一个从MAX 3SAT问题到MAX 3SAT-2问题K-归约.因为逼近MAX 3SAT问题在某个常数因子内是计算难解的,所以逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.这样作为推论也可以得到逼近MAX 3SAT-3问题在某个常数因子内是计算难解的,简化了以前关于逼近MAX 3SAT-3问题难解性的证明.In this paper,we show that it is hard to approximate MAX 3SAT-2 within some constant factor.We first introduce a new type of approximation preserving reduction.Using the new reduction,we reduce MAX 3SAT to MAX 3SAT-2.Since approximating MAX 3SAT within some constant factor is hard,approximating MAX 3SAT-2 within some constant factor is also hard.Furthermore,as a corollary,we also conclude that approximating MAX 3SAT-3 within some constant factor is NP-hard,which simplifies the previous proof.

关 键 词：NP-难解性 计算复杂性 近似性 

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