Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the size of minimal unsatisfiable formulas. | On the size of minimal unsatisfiable formulas Choongbum Lee y Submitted Oct 29 2008 Accepted Jan 21 2009 Published Jan 30 2009 Mathematics Subject Classihcation 05D99 Primary 05C15 68R10 Secondary Abstract An unsatishable formula is called minimal if it becomes satishable whenever any of its clauses are removed. We construct minimal unsatishable k-SAT formulas with Q nk clauses for k 3 thereby negatively answering a question of Rosenfeld. This should be compared to the result of Lovasz Studia Scientiarum Mathematicarum Hungarica 11 1974 p113-114 which asserts that a critically 3-chromatic k-uniform hypergraph can have at most fc2 J edges. 1 Introduction Given n boolean variables X1 . xn a literal is a variable xi or its negation xi 1 i n . A clause is a disjuction of literals and by k-clause we denote a clause of size k. A CNF Conjunctive Normal Form formula is a conjunction of clauses and a k-SAT formula is a CNF formula with only k-clauses. Throughout this article formula will mean a CNF formula and it will be given as a pair F V C with variables V x1 . xng and clauses C as collection of disjunction of literals V u V .A formula is called satisfiable if there exists an assignment of values to variables so that the formula becomes true. A formula is called minimal unsatisfiable if it is not satisfiable but removing any clause makes it satisfiable. Satisfiablity of a formula is closely related to the 2-colorability of a hypergraph in the following sense. A formula is satisfiable if there is an assignment of values to variables in a way that no clauses have only false literals inside it. Similarily a hypergraph is 2-colorable if there is a way to color the vertices into two colors so that none of the edges become monochromatic. A hypergraph H V E is called critically 3-chromatic if it is not 2 colorable but the deletion of any edge makes it 2 colorable. In this analogy minimal unsatisfiable formulas correspond to critically 3-chromatic hypergraphs. Therefore it is .
