[Math] Check Whether A Boolean Formula Has One Satisfying Assignment

computer sciencenp-complete

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 🙂

Best Answer

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

Related Question