Exact Cover is NP-complete #
EXACT COVER ([Karp 1972][karp1972reducibility]): is there a subfamily covering
every ground element exactly once? The problem lives on
FirstOrder.Language.setSystem unchanged (DescriptiveComplexity.ExactCover,
DescriptiveComplexity.Problems.SetFamily.Defs) – exactness is a property of the
subfamily, not a new vocabulary, and it replaces the threshold, so the marked
set plays no role at all.
Hardness comes from exactly-one satisfiability
(DescriptiveComplexity.Problems.OneInSat) by a reduction with no gadget and no
counting, order-free and of dimension 1:
- the ground elements are the variables and the clauses, a variable being an
element that occurs in some clause (
DescriptiveComplexity.SatOccurs); - the family has one set per literal
(x, s)of a variablex, namely{x} ∪ {clauses where (x, s) occurs}.
Covering the element x exactly once picks exactly one of the two literals of
x – that is a truth assignment – and covering a clause exactly once is
exactly what exactly-one satisfaction asks. Nothing here depends on the width
of the clauses, which is why the source is unrestricted 1-in-SAT rather than
its width-three restriction.
Equations
- One or more equations did not get rendered due to their size.
- DescriptiveComplexity.ExactCoverRed.instDecidableEqECTag.decEq DescriptiveComplexity.ExactCoverRed.ECTag.velt DescriptiveComplexity.ExactCoverRed.ECTag.velt = isTrue ⋯
- DescriptiveComplexity.ExactCoverRed.instDecidableEqECTag.decEq DescriptiveComplexity.ExactCoverRed.ECTag.velt (DescriptiveComplexity.ExactCoverRed.ECTag.lset s) = isFalse ⋯
- DescriptiveComplexity.ExactCoverRed.instDecidableEqECTag.decEq DescriptiveComplexity.ExactCoverRed.ECTag.celt DescriptiveComplexity.ExactCoverRed.ECTag.celt = isTrue ⋯
- DescriptiveComplexity.ExactCoverRed.instDecidableEqECTag.decEq DescriptiveComplexity.ExactCoverRed.ECTag.celt (DescriptiveComplexity.ExactCoverRed.ECTag.lset s) = isFalse ⋯
- DescriptiveComplexity.ExactCoverRed.instDecidableEqECTag.decEq (DescriptiveComplexity.ExactCoverRed.ECTag.lset s) DescriptiveComplexity.ExactCoverRed.ECTag.velt = isFalse ⋯
- DescriptiveComplexity.ExactCoverRed.instDecidableEqECTag.decEq (DescriptiveComplexity.ExactCoverRed.ECTag.lset s) DescriptiveComplexity.ExactCoverRed.ECTag.celt = isFalse ⋯
Instances For
Equations
- One or more equations did not get rendered due to their size.
The interpretation #
x is a variable of the formula – it occurs in some clause –, as a
formula. Without this guard an element in no clause would be a ground element
with two singleton sets to choose from: harmless for the existence of an exact
cover, and a factor two in their number.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Defining formula for the ground elements: the variables and the clauses.
Equations
- DescriptiveComplexity.ExactCoverRed.elemF DescriptiveComplexity.ExactCoverRed.ECTag.velt = DescriptiveComplexity.ExactCoverRed.occursF (0, 0)
- DescriptiveComplexity.ExactCoverRed.elemF DescriptiveComplexity.ExactCoverRed.ECTag.celt = DescriptiveComplexity.ThreeSatToSat.clF (0, 0)
- DescriptiveComplexity.ExactCoverRed.elemF (DescriptiveComplexity.ExactCoverRed.ECTag.lset s) = ⊥
Instances For
Defining formula for the family: one set per literal of a variable.
Equations
Instances For
Defining formula for incidence: the set of (x, s) contains the element
of x and the elements of the clauses where (x, s) occurs.
Equations
- One or more equations did not get rendered due to their size.
- DescriptiveComplexity.ExactCoverRed.memF x✝¹ x✝ = ⊥
Instances For
The interpretation of Exact Cover instances in CNF instances.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The points #
Characterization of the four relations #
The sets of the family are exactly the literal sets of the variables.
Correctness #
Stated for an explicit assignment and an explicit cover, so that the same
lemmas give the equivalence of the two decision problems and the bijection
between their solutions (DescriptiveComplexity.Problems.ExactCoverCounting).
The subfamily of an assignment: the sets of its true literals.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The assignment of a subfamily: the variables whose positive literal set is chosen.
Equations
Instances For
The true literals of an exactly-one assignment form an exact cover.
The chosen sets of an exact cover are the true literals of its assignment, at every variable.
An exact cover reads off an exactly-one assignment.
Correctness of the reduction: a CNF structure is exactly-one satisfiable iff its literal set system has an exact cover.
1-in-SAT FO-reduces to Exact Cover: the ground elements are the variables and the clauses, and the family has one set per literal. No order, no gadget and no counting.
Equations
- One or more equations did not get rendered due to their size.
Instances For
NP-completeness #
Exact Cover is NP-hard: 1-in-SAT, which is NP-hard, FO-reduces to it.
Exact Cover is NP-complete, derived from the first-order reductions of
this library and the Cook–Levin theorem.
Registered in the Lax archive as
Lax799700.SetFamily.exactCover_NP_complete.