The structure of the monoid of autarkies for clause-sets is investigated (autarkies are generalizations of satisfying (truth) assignments). The notion of a \plain clause-set" is introduced, where every clause is usable by some resolution refutation, and it is shown that a clause-set is plain i it has no non-trivial autarky. Every clause-set has a unique decomposition into a plain sub-clause-set and a satis able sub-clause-set. As a special case of autarkies we introduce the notion of \linear autarky," de nable by a system of linear inequalities over the rational numbers (and thus linear autarkies can be searched for in polynomial time by means of linear programming). Clause-sets without non-trivial linear autarkies we call \ weakly plain," and clause-sets satis able by a linear autarky we call \linearly satis able." As before, every clause-set has a unique decomposition into a weakly plain sub-clause-set and a linearly satis able sub-clause-set, but this time the decomposition is computable in polynomial time. The class of linearly satis able clause-sets seems to be a new and interesting polynomially decidable class of satis able clause-sets, generalizing the notion of a \matched clause-set" introduced in a recent paper by J. Franco and A. Van Gelder. The class of weakly plain clause-sets has some interesting combinatorial properties with respect to the \de ciency" = c ?n, the di erence of the number of clauses and the number of variables, introduced in the same paper: Among others (non-empty) weakly plain clause-sets ful ll 1, where this property has been known before only for minimally unsatis able clause-sets.
A systematic study of the notion of autarkies has been started in REF , where also the notion of linear autarkies has been introduced (manageable by linear programming in polynomial time).
Investigations on Autark Assignments
Discrete Applied Mathematics
Mathematics Computer Science