<p>The problem of deciding whether a given CNF formula has a satisfying assignment other than a given one is easily shown to be NP-complete by transforming a CNF formula to add one trivial solution.  This problem is called the “Another Solution Problem (ASP) of SAT” in [YS03], where it is used to give a systematic proof that (the decision versions of) the ASPs of many other problems are also NP-complete.</p>

<p>The problem of deciding whether a given CNF formula has a unique satisfying assignment or not (so you have to answer “no” if the formula has no satisfying assignments or more than one satisfying assignment) is <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aU#us">US</a>-complete.  US contains both <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aU#up">UP</a> and <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aC#conp">coNP</a>.</p>

<p>References</p>

<p>[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.</p>

<p><em>Edit</em>: An earlier version (revision 1) of this answer contained a confusion between the decision version and the search version.  It has been fixed.</p>

CC BY-SA 2.5
2010-09-24T19:57:18.497Z
Just a note: The NP-completeness of "another solution problem" is folklore, known long before 2003. (Maybe there is a reference from the 1970's, but the proof is so easy that I doubt it.)
Ryan Williams
CC BY-SA 2.5
2010-09-24T21:10:28.773Z
@Ryan: Thank you for the note.  I edited the answer to make the relation to [YS03] clearer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-24T15:22:07.283Z
2010-09-24T21:08:58.183Z
2010-09-24T21:08:58.183Z
Tsuyoshi Ito
<p>I recall Yoram Moses and myself studying this problem in the mid 1980s
(in light of some application) and discovering that for many natural NPC
problems the problem of finding a second/alternative solution
(or deciding whether such exists) is NPC.
We then found out that this was know, but I don't recall the ref,
and failed to find one (i.e., one predating the mid 1980s) now.
But I'm sure I do recall correctly the above.</p>

<p>Just a comment towards Ryan. The fact that a theorem can be given
as an exercise in current classes does not make it less appealing.
It should have been published in a paper bearing an adequate title
at the time that it was discovered...</p>

<p>Oded Goldreich</p>

CC BY-SA 2.5
2011-03-10T08:24:52.127Z
Hey, welcome aboard! I'm so excited to see you here :)
Sadeq Dousti
CC BY-SA 2.5
2011-03-10T08:15:49.217Z
2011-03-10T08:15:49.217Z
Oded Goldreich
<p>Here, I write an excerpt of the following paper:</p>

<p>Valiant, L. G. and Vazirani, V. V. 1986. NP is as easy as detecting unique solutions. <em>Theor. Comput. Sci.</em> 47, 1 (Nov. 1986), 85-93. DOI= <a href="http://dx.doi.org/10.1016/0304-3975(86)90135-0">http://dx.doi.org/10.1016/0304-3975(86)90135-0</a></p>

<blockquote>
  <p>For every known NP-complete problem, the number of solutions of its instances varies over a large range, from zero to exponentially many. It is therefore natural to ask if the inherent intractability of NP-complete problem is caused by this wide variation. We give a negative answer to this question using the notion of randomized polynomial time reducibility. We show that the problems of distinguishing between instances of SAT having zero or one solution, or of finding solutions to instances of SAT having a unique solution, are as hard as SAT, under randomized reductions.</p>
</blockquote>

<p>I also suggest looking at the relevant paper:</p>

<p>Beigel, R., Buhrman, H., and Fortnow, L. 1998. NP might not be as easy as detecting unique solutions. In <em>Proceedings of the Thirtieth Annual ACM Symposium on theory of Computing</em> (Dallas, Texas, United States, May 24 - 26, 1998). STOC '98. ACM, New York, NY, 203-208. DOI= <a href="http://doi.acm.org/10.1145/276698.276737">http://doi.acm.org/10.1145/276698.276737</a></p>

CC BY-SA 2.5
2010-09-25T11:13:00.173Z
2010-09-27T02:34:41.900Z
2010-09-27T02:34:41.900Z
Sadeq Dousti
<p>The first problem is NP-complete while the second one is the problem of Unique satsifiability which is Co-NP-hard and and its in the class $DP=\{(L_1 ∩ L_2)| L_1 \in NP, L_2\in CoNP\}$ (the intersection of NP set with Co-NP set).</p>

<p>Andreas Blass and Yuri Gurevich, 
<a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B7MFM-4DX44G9-139&amp;_user=10&amp;_coverDate=12%2F31%2F1982&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1472734416&amp;_rerunOrigin=google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=4e0484695afadc6228f2989839cd4caa&amp;searchtype=a">On the unique satisfiability problem,</a>
<a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B7MFM-4DX44G9-139&amp;_user=10&amp;_coverDate=12%2F31%2F1982&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1472734416&amp;_rerunOrigin=google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=4e0484695afadc6228f2989839cd4caa&amp;searchtype=a"></a></p>

CC BY-SA 2.5
2010-09-24T15:32:17.903Z
A small point: The second problem is not a promise problem.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-24T15:37:47.370Z
I had realized that and fixed it, but thanks for spotting it anyway!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-24T15:41:29.177Z
By the way, I did not copy anything from your answer, so I have no idea what your following comment refers to: “When you copy from another answer, please indicate that.”  I copied the reference of my answer from another post of mine on MathOverflow (http://mathoverflow.net/questions/31251/how-to-combine-linear-constraints-on-a-matrix-and-its-inverse/36373#36373), but I do not think that you are referring to this.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-24T15:18:51.730Z
2010-09-24T17:09:29.347Z
2010-09-24T17:09:29.347Z
Mohammad Al-Turkistany
<p>The solution to both problems, UNIQUE SAT as well as ANOTHER SAT, with a complete classification of complexity, can be found in the paper</p>

<p>L. Juban: Dichotomy theorem for the generalized unique satisfiability problem   <a href="http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27" rel="nofollow">http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27</a></p>

CC BY-SA 3.0
2014-01-27T14:44:32.350Z
2014-01-27T14:44:32.350Z
Miki Hermann
<p>Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ?</p>

<p>What is the complexity of this problem ? (It most surely is in NP, but is it also NP-hard ?)</p>

<p>What if you are not given the assignment and you just want do decide whether the formula has a unique satisfying assignment ?</p>

<p>Thanks.</p>

CC BY-SA 2.5
2011-03-10T11:11:12.370Z
@Hsien-Chih Chang, we had Oded's name on the front page before your retag, retagging is not urgent, it would be nice if his name remained there a little longer. :)
Kaveh
CC BY-SA 2.5
2011-03-10T11:48:34.603Z
@Kaveh: Oops, sorry. I guess I somehow assume that he will stay and constantly provide more and more good answers, so his name will be appeared frequently on the main page :)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-10T11:55:49.293Z
@Hsien-Chih Chang, I also hope so. :)
Kaveh
CC BY-SA 2.5
2010-09-24T19:59:22.163Z
Your first problem is often a homework exercise. Hint: given any formula F, design a formula F' where the all-zeroes assignment trivially satisfies it, and there exists a second satisfying assignment F' iff F is satisfiable.
Ryan Williams
<cc.complexity-theory><np-hardness><sat><unique-solution>
Verifying unique solutions of SAT
J--
# Verifying unique solutions of SAT

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

Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ?

What is the complexity of this problem ? (It most surely is in NP, but is it also NP-hard ?)

What if you are not given the assignment and you just want do decide whether the formula has a unique satisfying assignment ?

Thanks.

**Tags:** cc.complexity-theory, np-hardness, sat, unique-solution

> **Comments:**
> **username_3**: Your first problem is often a homework exercise. Hint: given any formula F, design a formula F' where the all-zeroes assignment trivially satisfies it, and there exists a second satisfying assignment F' iff F is satisfiable.  
> **username_1**: @Hsien-Chih Chang, we had Oded's name on the front page before your retag, retagging is not urgent, it would be nice if his name remained there a little longer. :)  
> **username_2**: @username_1: Oops, sorry. I guess I somehow assume that he will stay and constantly provide more and more good answers, so his name will be appeared frequently on the main page :)  
> **username_1**: @Hsien-Chih Chang, I also hope so. :)  

---

## 5 answers

### Answer by username_4 on 2010-09-24. Score: 31

The problem of deciding whether a given CNF formula has a satisfying assignment other than a given one is easily shown to be NP-complete by transforming a CNF formula to add one trivial solution. This problem is called the “Another Solution Problem (ASP) of SAT” in [YS03], where it is used to give a systematic proof that (the decision versions of) the ASPs of many other problems are also NP-complete.

The problem of deciding whether a given CNF formula has a unique satisfying assignment or not (so you have to answer “no” if the formula has no satisfying assignments or more than one satisfying assignment) is [US](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aU#us)-complete. US contains both [UP](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aU#up) and [coNP](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aC#conp).

References

[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.

*Edit*: An earlier version (revision 1) of this answer contained a confusion between the decision version and the search version. It has been fixed.

> **Comments:**
> **username_3**: Just a note: The NP-completeness of "another solution problem" is folklore, known long before 2003. (Maybe there is a reference from the 1970's, but the proof is so easy that I doubt it.)  
> **username_4**: @Ryan: Thank you for the note.  I edited the answer to make the relation to [YS03] clearer.  

---

### Answer by username_5 on 2011-03-10. Score: 24

I recall Yoram Moses and myself studying this problem in the mid 1980s
(in light of some application) and discovering that for many natural NPC
problems the problem of finding a second/alternative solution
(or deciding whether such exists) is NPC.
We then found out that this was know, but I don't recall the ref,
and failed to find one (i.e., one predating the mid 1980s) now.
But I'm sure I do recall correctly the above.

Just a comment towards Ryan. The fact that a theorem can be given
as an exercise in current classes does not make it less appealing.
It should have been published in a paper bearing an adequate title
at the time that it was discovered...

username_5

> **Comments:**
> **username_6**: Hey, welcome aboard! I'm so excited to see you here :)  

---

### Answer by username_6 on 2010-09-25. Score: 13

Here, I write an excerpt of the following paper:

Valiant, L. G. and Vazirani, V. V. 1986. NP is as easy as detecting unique solutions. *Theor. Comput. Sci.* 47, 1 (Nov. 1986), 85-93. DOI= <http://dx.doi.org/10.1016/0304-3975(86)90135-0>

> For every known NP-complete problem, the number of solutions of its instances varies over a large range, from zero to exponentially many. It is therefore natural to ask if the inherent intractability of NP-complete problem is caused by this wide variation. We give a negative answer to this question using the notion of randomized polynomial time reducibility. We show that the problems of distinguishing between instances of SAT having zero or one solution, or of finding solutions to instances of SAT having a unique solution, are as hard as SAT, under randomized reductions.

I also suggest looking at the relevant paper:

Beigel, R., Buhrman, H., and Fortnow, L. 1998. NP might not be as easy as detecting unique solutions. In *Proceedings of the Thirtieth Annual ACM Symposium on theory of Computing* (Dallas, Texas, United States, May 24 - 26, 1998). STOC '98. ACM, New York, NY, 203-208. DOI= <http://doi.acm.org/10.1145/276698.276737>


---

### Answer by username_7 on 2010-09-24. Score: 7

The first problem is NP-complete while the second one is the problem of Unique satsifiability which is Co-NP-hard and and its in the class $DP=\{(L\_1 ∩ L\_2)| L\_1 \in NP, L\_2\in CoNP\}$ (the intersection of NP set with Co-NP set).

Andreas Blass and Yuri Gurevich,
[On the unique satisfiability problem,](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B7MFM-4DX44G9-139&_user=10&_coverDate=12%2F31%2F1982&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1472734416&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=4e0484695afadc6228f2989839cd4caa&searchtype=a)

> **Comments:**
> **username_4**: A small point: The second problem is not a promise problem.  
> **username_4**: I had realized that and fixed it, but thanks for spotting it anyway!  
> **username_4**: By the way, I did not copy anything from your answer, so I have no idea what your following comment refers to: “When you copy from another answer, please indicate that.”  I copied the reference of my answer from another post of mine on MathOverflow (http://mathoverflow.net/questions/31251/how-to-combine-linear-constraints-on-a-matrix-and-its-inverse/36373#36373), but I do not think that you are referring to this.  

---

### Answer by username_8 on 2014-01-27. Score: 3

The solution to both problems, UNIQUE SAT as well as ANOTHER SAT, with a complete classification of complexity, can be found in the paper

L. Juban: Dichotomy theorem for the generalized unique satisfiability problem <http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27>


---

