计算机科学与探索2013，Vol.7Issue(8)：691-697,7.DOI:10.3778/j.issn.1673-9418.1305025
一个正则NP-完全问题及其不可近似性
A Regular NP-Complete Problem and Its Inapproximability
摘要
Abstract
A CNF (conjunctive normal form) formula can be transformed into another formula with some special structures or properties by a proper reduction transformation,such that two formulas have the same satisfiability.The factor graphs of CNF formulas with regular structures have some well properties and known results in theory of graph,which may be applied to investigating the satisfiability and complexity of formulas.The minimal unsatisfiable formulas have a critical characterization,which the formula itself is unsatisfiable and the resulting formula moving anyone clause from the original formula is satisfiable.By this critical characterization,this paper presents a polynomial reduction from a 3-CNF formula to a regular (3,4)-CNF formula,in which each clause contains exactly three literals,and each variable appear exactly four times.Therefore,the regular (3,4)-SAT is a NP-complete problem,and MAX (3,4)-SAT is inapproximable.关键词
极小不可满足性/正则(3,4)-CNF公式/NP-完全性/不可近似性Key words
minimal unsatisfiability/ regular (3, 4)-CNF formula/ NP-completeness/ inapproximability分类
信息技术与安全科学引用本文复制引用
许道云,王晓峰..一个正则NP-完全问题及其不可近似性[J].计算机科学与探索,2013,7(8):691-697,7.基金项目
The National Natural Science Foundation of China under Grant No.61262006(国家自然科学基金). （国家自然科学基金）
