Citation
Xs. Zhao et Dc. Ding, Two tractable subclasses of minimal unsatisfiable formulas, SCI CHINA A, 42(7), 1999, pp. 720-731
Citations number
6
Categorie Soggetti
Multidisciplinary
Journal title
SCIENCE IN CHINA SERIES A-MATHEMATICS PHYSICS ASTRONOMY
ISSN journal
10016511
→ ACNP
Volume
42
Issue
7
Year of publication
1999
Pages
720 - 731
Database
ISI
SICI code
1001-6511(199907)42:7<720:TTSOMU>2.0.ZU;2-O
Abstract
The minimal unsatisfiability problem is considered of the propositional for
mula in CNF which in the case of variables x(1),...,x(pi) consist of n + k
clauses including x(1) V...V x(pi) and ] x(1) V...V] x(pi). It is shown tha
t when k less than or equal to 4 the minimal unsatisfiability problem can b
e solved in polynomial time.