Finiteness conjecture for non-singular unsatisfiable hitting clause-sets

A clause-set is hitting if every two distinct clauses C,CC,C' clash in at least one variable, that is, CC1\lvert C\cap\overline{C'}\rvert\geq 1. A clause-set is non-singular in the sense used in the paper, and its deficiency is denoted by kNk\in\mathbb{N}. Two clause-sets have the same isomorphism type when they are isomorphic under the relevant variable and clause structure.

Finiteness conjecture. For every deficiency kNk\in\mathbb{N}, 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.