Motivated by the NP-completeness of Another-SAT problem, Another-3SAT={$(\phi, m)$: 3CNF formula $\phi$ has a satisfying assignment different from $m$ }, Let us consider a function from all uniquely satisfiable Horn 3SAT formulas on $n$ variables to binary strings of length $n$ (representing unique solutions). I'm interested in the density of the range of this function. A set is sparse if the number of strings in the set of length $n$ is bounded by a polynomial in $n$ otherwise it is dense. What is the best known lower-bound for the asymptotic growth rate of the number of distinct satisfying assignments for uniquely satisfiable Horn 3SAT formulas on $n$ variables? Is this set dense?EDIT: Thanks to Tsuyoshi,I realized that the original question had a mistake. So I changed the question to be about uniquely satisfiable Horn 3SAT.
Density of distinct satisfying assignments for uniquely satisfiable formulas
cc.complexity theory