31
$\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.

Improve this question
$\endgroup$
4
  • 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
    Commented Sep 24, 2010 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
    Commented Mar 10, 2011 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 張顯之
    Commented Mar 10, 2011 at 11:48
  • $\begingroup$ @Hsien-Chih Chang, I also hope so. :) $\endgroup$
    – Kaveh
    Commented Mar 10, 2011 at 11:55

5 Answers 5

Reset to default
31
$\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.

Improve this answer
$\endgroup$
2
  • 7
    $\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
    Commented Sep 24, 2010 at 19:57
  • $\begingroup$ @Ryan: Thank you for the note. I edited the answer to make the relation to [YS03] clearer. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 24, 2010 at 21:10
24
$\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

Improve this answer
$\endgroup$
1
  • 16
    $\begingroup$ Hey, welcome aboard! I'm so excited to see you here :) $\endgroup$
    – Sadeq Dousti
    Commented Mar 10, 2011 at 8:24
13
$\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

Improve this answer
$\endgroup$
7
$\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,

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ A small point: The second problem is not a promise problem. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 24, 2010 at 15:32
  • 1
    $\begingroup$ I had realized that and fixed it, but thanks for spotting it anyway! $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 24, 2010 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
    Commented Sep 24, 2010 at 15:41
3
$\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

Improve this answer
$\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.