ProbXiv
Explorersign in
Problem archiveProblem record

Statement

A clause-set is hitting if every two distinct clauses C,C′C,C' clash in at least one variable, that is, ∣C∩C′‾∣≥1\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 k∈Nk\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 k∈Nk\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.