# 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)

• This sounds very similar to 3-dimensional matching. Feb 18 '17 at 22:40
• I think the right term of this class is UP? Feb 19 '17 at 9:14
• @WillardZhan : ​ That's just a different class. ​ ​ ​ ​
– user12859
Feb 20 '17 at 0:21
• @RickyDemer Oh, I see. Multiple certificates in this class indicate a 'no' instance. Feb 20 '17 at 2:04

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