# Density of distinct satisfying assignments for uniquely satisfiable formulas

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.

• For every truth assignment x, there exists a 3CNF formula whose unique satisfying assignment is x, meaning that the range of your function consists of all n-bit strings. Not sure if this is what you are asking about. – Tsuyoshi Ito Mar 21 '12 at 14:24
• In your construction, how many variables do you need for n-bit strings? – Mohammad Al-Turkistany Mar 21 '12 at 15:49
• I need n variables, of course, but I do not know what you mean. According to your definition, an n-bit string can result only from an n-variable 3CNF formula. – Tsuyoshi Ito Mar 21 '12 at 15:57
• Does your construction work for 3CNF clauses with three distinct leterals? – Mohammad Al-Turkistany Mar 21 '12 at 16:07

If I understand your question correctly, you are asking for asymptotic growth of $f:\mathbb{N} \to \mathbb{N}$ such that $f(n)=k$ iff there are $k$ different 3-CNF formulas on $n$ variables such that each of them has a unique satisfying assignment. As Tsuyoshi Ito, points out you can construct a 3-SAT instance $\phi$ from a given Boolean string $x=b_{n-1},\dots,b_0$ such that $x$ is the only satisfying assignment of $\phi$. This follows from Cook-Levin, theorem as you can write description of T.M which accepts the input iff the input bit string $y$ is equal to $x$, and then using the Cook-Levin construction convert it into a 3-SAT formula where the variables would correspond to input bits. But size of $\phi$ can be polynomial in $n$ (I am not sure if Tsuyoshi Ito was referring to this construction). Also Valiant-Vazirani lemma which sates that 3-SAT instance on $n$ variables can be reduced (using a randomized algorithm which succeeds on $\frac{1}{8n}$ fraction of random choices) to U-SAT, can be used to deduce that from a 3-SAT instance $\phi$ on $n$ variable we get at least $\frac{1}{8n}$ 3-SAT instances on $2n$ variables (Valiant-Vazirani lemma uses hash functions, and the number of variables it adds to the formula is $k \in [n]$, which denotes the logarithm of number of satisfying assignments of the old formula, and hence to make the formula obtained by the randomized algorithm in the reduction uniformly on $2n$ variables we'll add clauses involving dummy variables). Hence $f(2n)\geq \frac{1}{8n}2^{r(n}g(n)$ where $g(n)$ is the number of different 3-SAT instances and $r(n)$ is the randomness used by Valiant-Vazirani reduction..