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)
Thanks in advance!!!