Finiteness conjecture for non-singular unsatisfiable hitting clause-sets
Finiteness conjecture for non-singular unsatisfiable hitting clause-sets
A clause-set is hitting if every two distinct clauses clash in at least one variable, that is, . A clause-set is non-singular in the sense used in the paper, and its deficiency is denoted by . Two clause-sets have the same isomorphism type when they are isomorphic under the relevant variable and clause structure.
Finiteness conjecture. For every deficiency , there are only finitely many isomorphism types of non-singular unsatisfiable hitting clause-sets.
This is presented as the main conjecture motivating the classification of minimally unsatisfiable clause-sets by deficiency, especially the classification of unsatisfiable hitting clause-sets. The supplied text gives no resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Oliver Kullmann and Xishun Zhao, “On variables with few occurrences in conjunctive normal forms”, arXiv:1010.5756 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.