# Is UNIQUE-X3C a US-complete problem?

The problem: Exact Cover by 3-Sets (X3C)

The definition: Given a set X, with |X| = 3q (so, the size of X is a multiple of 3), and a collection C of 3-element subsets of X. Can we find a subset C’ of C where every element of X occurs in exactly one member of C’? (So, C’ is an “exact cover” of X).

The class US (Unique Polynomial-Time) is the class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.

UNIQUE-3SAT is the problem of deciding whether the 3CNF Boolean formulas have a unique solution. UNIQUE-3SAT is a known US-complete problem.

Is the version of problem Exact Cover by 3-Sets(UNIQUE-X3C) when the instances have a unique solution a US-complete problem? (which means there is a unique subset C’ as solution)

Thus, $\mathrm{UNIQUE-3SAT}$ many-one reduces to $\mathrm{UNIQUE-X3C}$. As a consequence, $\mathrm{UNIQUE-X3C}$ is $\mathrm{US}$-complete.