A Lower Bound on Max-SAT for Regular(3,4)-CNF
A regular (3, 4)-CNF formula F is a 3-CNF formula, where each variable occurs exactly four times in F.A regular (3, 4, u)-CNF formula F is a regular (3, 4)-CNF formula, where each variable occurs u times positively in F, u is a integer no more than four.The regular (3,4)-SAT problem is the satisfiability problem restricted to regular (3, 4)-CNF formulas.It is known that regular (3, 4)-SAT is NP-Complete.In this paper, we give a lower bound on MAX-SAT for regualr (3,4)-CNF formula, sat(F) ≥ 17/20m for a regular (3, 4, 3)-CNF formula F and sat(F) ≥3/4m for a regular (3, 4, 2)-CNF formula F, where sat(F) is the maximal number of clauses that can be satisfied by a truth assignment, m is the number of clauses of F.
MAX-SAT Lower bound regular (3,4,u)-CNF formula bipartite cover set clause cover set
Cunkuan Dai Daoyun Xu
College of Computer Science and Technology,Guizhou University,Guiyang (550025),P.R.China;School of E College of Computer Science and Technology,Guizhou University,Guiyang (550025),P.R.China
国内会议
金华
英文
1-10
2015-10-30（万方平台首次上网日期，不代表论文的发表时间）