25
$\begingroup$

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.

$\endgroup$
  • 13
    $\begingroup$ 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. $\endgroup$ – Ryan Williams Sep 24 '10 at 19:59
  • 1
    $\begingroup$ @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. :) $\endgroup$ – Kaveh Mar 10 '11 at 11:11
  • 1
    $\begingroup$ @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 :) $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 10 '11 at 11:48
  • $\begingroup$ @Hsien-Chih Chang, I also hope so. :) $\endgroup$ – Kaveh Mar 10 '11 at 11:55
27
$\begingroup$

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-complete. US contains both UP and 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.

$\endgroup$
  • 6
    $\begingroup$ 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.) $\endgroup$ – Ryan Williams Sep 24 '10 at 19:57
  • $\begingroup$ @Ryan: Thank you for the note. I edited the answer to make the relation to [YS03] clearer. $\endgroup$ – Tsuyoshi Ito Sep 24 '10 at 21:10
22
$\begingroup$

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

Oded Goldreich

$\endgroup$
  • 15
    $\begingroup$ Hey, welcome aboard! I'm so excited to see you here :) $\endgroup$ – M.S. Dousti Mar 10 '11 at 8:24
12
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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,

$\endgroup$
  • 1
    $\begingroup$ A small point: The second problem is not a promise problem. $\endgroup$ – Tsuyoshi Ito Sep 24 '10 at 15:32
  • 1
    $\begingroup$ I had realized that and fixed it, but thanks for spotting it anyway! $\endgroup$ – Tsuyoshi Ito Sep 24 '10 at 15:37
  • 6
    $\begingroup$ 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 (mathoverflow.net/questions/31251/…), but I do not think that you are referring to this. $\endgroup$ – Tsuyoshi Ito Sep 24 '10 at 15:41
2
$\begingroup$

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

$\endgroup$

Your Answer

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

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