| 逼近MAX 3SAT-2问题的难解性（英文） |
| |
| 引用本文： | 陈文彬.逼近MAX 3SAT-2问题的难解性（英文）[J].广州大学学报(综合版),2012(2):6-9. |
| |
| 作者姓名： | 陈文彬 |
| |
| 作者单位： | 广州大学计算机科学与教育软件学院,广东广州510006 |
| |
| 摘 要： | 证明了逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.首先引进了一种保留近似算法难解性的K-归约的概念;然后给出了一个从MAX 3SAT问题到MAX 3SAT-2问题K-归约.因为逼近MAX 3SAT问题在某个常数因子内是计算难解的,所以逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.这样作为推论也可以得到逼近MAX 3SAT-3问题在某个常数因子内是计算难解的,简化了以前关于逼近MAX 3SAT-3问题难解性的证明.
|
| 关 键 词： | NP-难解性 计算复杂性 近似性 |
Hardness of approximating MAX 3SAT-2 |
| |
| CHEN Wen-bin.Hardness of approximating MAX 3SAT-2[J].Journal of Guangzhou University,2012(2):6-9. |
| |
| Authors: | CHEN Wen-bin |
| |
| Institution: | CHEN Wen-bin (School of Computer Science and Education Software,Guangzhou University,Guangzhou 510006,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | NP-hardness computational complexity approximation |
| 本文献已被 维普 等数据库收录！ |
