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

Hardness of approximating MAX 3SAT-2

证明了逼近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.