Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I'm reviewing old homeworks for an upcoming comp sci test and I came across this question:

Say whether the following statement is True, False or Unknown:

The problem of checking whether a given Boolean formula has exactly one satisfying assignment, is NP-complete

My original answer to this was True because it seems to me that you can reduce SAT to this. Here's my solution:

Let's call this problem EX_SAT. Given a boolean formula s, we can construct a TM M where L(M) = SAT using EX_SAT. Assume that we have a NTM P that decides EX_SAT, and a NTM Q that decides DOUBLE_SAT (the problem of determining whether a Boolean formula has two or more satisfying assignments). We that DOUBLE_SAT is NP-complete because we reduced SAT to it in an earlier homework problem.

M = on input s
    1. Run P on s.
    2. If P accepts, then accept.
    3. If P rejects then run Q on s.
    4. If Q accepts then accept.
    5. If Q rejects then reject.

I see that EX_SAT doesn't have a polynomial time verifier, and I also see the one flaw in this proof is that I also have to use DOUBLE_SAT to complete it - which probably doesn't allow us to conclude that EX_SAT is NP-complete, but I thought I would ask this here because it might aid in my understanding of the topic.

Any thoughts would be much appreciated :)

share|improve this question

migrated from stackoverflow.com Dec 14 '11 at 21:56

This question came from our site for professional and enthusiast programmers.

2 Answers 2

up vote 0 down vote accepted

I believe that this is an open problem because I think that the problem of "does φ have exactly one satisfying assignment?" is, I believe, co-NP-complete by a reduction from the unsatisfiability problem, which is known to be co-NP-complete. The idea is that given a formula φ with variables v1, v2, ..., vn, we can construct the formula φ' as

φ' = (φ ∨ w) ∧ (w → ¬ v1) ∧ (w → ¬ v2) ∧ ... ∧ (w → ¬ vn)

The idea behind φ' is that if φ is unsatisfiable, this has exactly one satisfying assignment: make the new variable w true and make each vi false. Otherwise, for each satisfying assignment of φ, there is one satisfying assignment to φ' formed by using the satisfying assignment to φ with w set to false. This reduction can be computed in polynomial-time, so the problem of "does φ have exactly one satisfying assignment?" is co-NP-hard. Since it's also in co-NP (because you can easily verify a "no" answer given a certificate containing two satisfying assignments), this problem is NP-complete. Since it's unknown whether NP = co-NP, no co-NP-complete problem is known to be in NP. Thus it's an open problem whether this problem is also contained in NP, though I think the general conjecture is "no."

Hope this helps!

share|improve this answer
    
"because you can easily verify a "no" answer given a certificate containing two satisfying assignments" - what if the formula has no satisfying assignments? I'm pretty sure that exactly-1-SAT is in $\Sigma_2^p\cap\Pi_2^p$, but not known to be lower. –  Aubrey da Cunha Dec 16 '11 at 5:34
    
Ah, I hadn't thought of that! Thanks for pointing that out! –  templatetypedef Dec 16 '11 at 6:41

For the problem to be NP-complete it has to be in NP, which means it has to have a polynomial time verifier for all "yes" answers. If the exactly-1-satisfying-assignment question is in NP, that means there must be "yes" answers and verifiers for the following two questions:

Does this formula have a satisfying assignment? Does this formula have no more satisfying assignments?

There's a polynomial time verifier for the first question, but not the second unless NP = coNP. Since the status NP = coNP is unknown, the status of the main question also has to be "unknown."

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.