关键词: 极小不可满足性, 正则(3, 4)-CNF公式, NP-完全性, 不可近似性

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.

Key words: minimal unsatisfiability, regular (3, 4)-CNF formula, NP-completeness, inapproximability