Bounds for variables with few occurrences in conjunctive normal forms
arXiv:1408.0629
Abstract
We investigate connections between SAT (the propositional satisfiability problem) and combinatorics, around the minimum degree (number of occurrences) of variables in various forms of redundancy-free boolean conjunctive normal forms (clause-sets). Lean clause-sets do not have non-trivial autarkies, that is, it is not possible to satisfy some clauses and leave the other clauses untouched. The deficiency of a clause-set is the difference of the number of clauses and the number of variables. We prove a precise upper bound on the minimum variable degree of lean clause-sets in dependency on the deficiency. If a clause-set does not fulfil this upper bound, then it must have a non-trivial autarky; we show that the autarky-reduction (elimination of affected clauses) can be done in polynomial time, while it is open to find the autarky itself in polynomial time. Then we investigate this upper bound for the special case of minimally unsatisfiable clause-sets. We show that the bound can be improved here, introducing a general method to improve the underlying recurrence. We consider precise relations, and thus the investigations have a number-theoretical flavour. We try to build a bridge from logic to combinatorics (especially to hypergraph colouring), and we discuss thoroughly the background and open problems, and provide many examples and explanations.
arXiv comment103 pages; second version has changed style, various small errors and typos corrected, and improved presentation of results, third version with editorial improvements, fourth version with editorial corrections and improvements/updates, fifth version with complete literature update and improved proofs and presentation; continues arXiv:1010.5756
References in corpus (6)
- Satisfiability of Acyclic and Almost Acyclic CNF Formulas
- On the van der Waerden numbers w(2;3,t)
- Computing maximal autarkies with few and simple oracle queries
- On variables with few occurrences in conjunctive normal forms
- On the construction of non-2-colorable uniform hypergraphs
- The Local Lemma is asymptotically tight for SAT