On Computing Minimum Unsatisfiable Cores
Inês Lynce, João P. Marques-Silva · ePrints Soton (University of Southampton) · 2004
Abstract. Certifying a SAT solver for unsatisfiable instances is a computationally hard problem. Nevertheless, in the utilization of SAT in industrial settings, one often needs to be able to generate unsatisfiability proofs, either to guarantee the correctness of the SAT solver or as part of the utilization of SAT in some applications (e.g. in model checking). As part of the process of generating unsatisfiable proofs, one is also interested in unsatisfiable subformulas of the original formula, also known as unsatisfiable cores. Furthermore, it may by useful identifying the minimum unsatisfiable core of a given problem instance, i.e. the smallest number of clauses that make the instance unsatisfiable. This approach is be very useful in AI problems where identifying the minimum core is crucial for correcting the minimum amount of inconsistent information (e.g. in knowledge bases). 1