I was solving an awfully hard sudoku and at some point, the fact that there is exactly one assignment helped to exclude a number in some cell which helped me finishing it.
This got me wondering in terms of the SAT problem. First of all suppose we get a SAT and we know there is exactly one assignment, how fast can we get the assignment ? Second, if we get a SAT and we know there is at most one satisfying assignment, how fast can we know if it is satisfiable (and find the assignment) ?
Intuitively it feels like it should be polynomial for the first one, and it also feels like SAT could be reduced in polynomial time to the second one (maybe by trying to add closes ?), but I have no idea on how to show any of those, I think that we can only consider 3-SAT for simplicity.
If finding solutions for NP-complete problems that have exactly one solution is easy, then all of NP is easy.
This was shown by Valiant and Vazirani in their seminal paper "NP is as easy as detecting unique solutions". They give a randomized polynomial-time reduction from SAT to a series of SAT instances, one of which has exactly one solution with a low but significant probability. If you run the reduction a polynomial number of times, selecting from the instances at random each time, the probabilty approaches 1 that an instance with a unique solution will be selected. If finding solutions to such instances is easy, then SAT is easy as well--- just feed the hard SAT instance into this reduction repeatedly until you get an easy instance.
Given that most theoretical computer scientists don't think SAT is easy, SAT with exactly one solution isn't expected to be easy, either.