𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency

✍ Scribed by Hans Kleine Büning; Xishun Zhao

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
72 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We say a propositional formula F in conjunctive normal form is represented by a formula H and a homomorphism φ, if φ(H ) = F . A homomorphism is a mapping consisting of a renaming and an identification of literals. The deficiency of a formula is the difference between the number of clauses and the number of variables. We show that for fixed k 1 and t 1 each minimal unsatisfiable formula with deficiency k can be represented by a formula H with deficiency t and a homomorphism and such a representation can be computed in polynomial time.

📜 SIMILAR VOLUMES

Polynomial time algorithms for minimizin
Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
✍ Philippe Baptiste 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 102 KB 👁 2 views

We study the problem of minimizing the weighted number of late jobs to be scheduled on a single machine when processing times are equal. In this paper, we show that this problem, as well as its preemptive variant, are strongly polynomial. When preemption is not allowed ( 1"p H "p, r H " w H ; H ), t