5
$\begingroup$

Using the result by Valiant and Vazirani, we know that Unique-3SAT (3SAT with a unique solution) is hard unless NP=RP. Also it is widely believed that the "Unique" version of any NP-complete problem admits the same result comment after Theorem 2.1.

However, there are NP-complete problems whose instances admit only zero or more than one feasible solutions. Consider, NAE-3SAT where in each feasible solution, each clause must have at least one true and at least one false literal. Thus, by definition, the complement (make true to false and false to true for all variables) of any feasible assignment is also feasible. Thus this problem can have zero or more than one solutions.

Is it possible, to find a parsimonious reduction from Unique-3SAT to Unique-NAE-3SAT? How do you preserve the number of solutions in such a reduction? If there is no such reduction, then is not the widely believed statement as mentioned above is false?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ I don’t understand the question. As you observed, NAE-3SAT never has a unique solution, hence Unique-NAE-3SAT is an empty problem, and you cannot reduce anything else to it, irrespective of if your reduction is parsimonious or not. $\endgroup$ – Emil Jeřábek Sep 25 '18 at 8:57
  • 1
    $\begingroup$ Even if the Unique-NAE-3SAT is a typo for NAE-3SAT, it still makes no sense. There cannot be a parsimonious reduction of Unique-3SAT to NAE-3SAT, as the latter never has a unique solution. So what is the question? $\endgroup$ – Emil Jeřábek Sep 25 '18 at 9:25
  • 1
    $\begingroup$ Oh, now I’ve seen the link. First, there is no “widely believed” in the text anywhere. Second, this is clearly a copy-and-paste error of the identical comment after Theorem 2.2. Even there, it is not meant as any kind of conjecture that this holds literally for all NP-complete problems; it is just an empirical observation that it holds for typical natural NP-complete problems. $\endgroup$ – Emil Jeřábek Sep 25 '18 at 9:36
  • 4
    $\begingroup$ I agree with Emil. However, I think the question becomes sensicial if you consider the following variant of NAE-3SAT, let's call it half-NAE-3SAT: an instance consists of an NAE-3SAT formula and a single literal, and a valid solution must make both the formula and the literal true. This removes the involution mentioned in the OQ, and so can plausibly have unique solutions. And yet it is still morally equivalent to NAE-3SAT (and also technically equivalent, probably in more than one way). $\endgroup$ – Joshua Grochow Sep 25 '18 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.