<p>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 <a href="http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf" rel="noreferrer">comment after Theorem 2.1</a>. </p>

<p>However, there are NP-complete problems whose instances admit only zero or more than one feasible solutions. Consider, <a href="http://ahttps://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability" rel="noreferrer">NAE-3SAT</a> 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. </p>

<p>Is it possible, to find a <a href="https://en.wikipedia.org/wiki/Parsimonious_reduction" rel="noreferrer">parsimonious reduction</a> 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?    </p>

CC BY-SA 4.0
2018-09-25T08:57:44.803Z
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.
Emil Jeřábek
CC BY-SA 4.0
2018-09-25T09:25:35.500Z
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?
Emil Jeřábek
CC BY-SA 4.0
2018-09-25T09:36:10.433Z
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.
Emil Jeřábek
CC BY-SA 4.0
2018-09-25T11:37:47.680Z
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).
Joshua Grochow
<cc.complexity-theory><counting-complexity>
Parsimonious Reduction from Unique-3SAT to NAE-3SAT
Sayan Bandyapadhyay
# Parsimonious Reduction from Unique-3SAT to NAE-3SAT

(Asked by: username_0 on 2018-09-24)

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](http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf).

However, there are NP-complete problems whose instances admit only zero or more than one feasible solutions. Consider, [NAE-3SAT](http://ahttps://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability) 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](https://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, counting-complexity
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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?  
> **username_1**: 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.  
> **username_2**: 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).  

---

## 0 answers

