1
$\begingroup$

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!!!

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

1 Answer 1

1
$\begingroup$

Yes, it is.

This scanned chapter 3 from Garey-Johnson classic book describe a parsimonious reduction from 3SAT to 3DM. And X3C is a generalization of 3DM. So, the same reduction can be used to parsimoniously reduce 3SAT to 3DM.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.