Title: XSAT of Linear CNF Formulas,
Abstract: Open questions with respect to the computational complexity of linear CNF
formulas in connection with regularity and uniformity are addressed. In
particular it is proven that any l-regular monotone CNF formula is
XSAT-unsatisfiable if its number of clauses m is not a multiple of l. For exact
linear formulas one finds surprisingly that l-regularity implies k-uniformity,
with m = 1 + k(l-1)) and allowed k-values obey k(k-1) = 0 (mod l). Then the
computational complexity of the class of monotone exact linear and l-regular
CNF formulas with respect to XSAT can be determined: XSAT-satisfiability is
either trivial, if m is not a multiple of l, or it can be decided in
sub-exponential time, namely O(exp(n^^1/2)). Sub-exponential time behaviour for
the wider class of regular and uniform linear CNF formulas can be shown for
certain subclasses.