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