Check Whether A Boolean Formula Has One Satisfying Assignment

Question

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 :)

Answer 1

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 v₁, v₂, ..., v_n, we can construct the formula φ' as

φ' = (φ ∨ w) ∧ (w → ¬ v₁) ∧ (w → ¬ v₂) ∧ ... ∧ (w → ¬ v_n)

The idea behind φ' is that if φ is unsatisfiable, this has exactly one satisfying assignment: make the new variable w true and make each v_i 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!

Answer 2

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 of NP = coNP is unknown, the status of the main question also has to be "unknown."