<p>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..  </p>

CC BY-SA 3.0
2012-03-21T17:16:54.497Z
2012-03-23T13:34:54.977Z
2012-03-23T13:34:54.977Z
Sajin Koroth
<p>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. </p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-21T14:24:07.103Z
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
CC BY-SA 3.0
2012-03-21T15:49:32.513Z
In your construction, how many variables do you need for n-bit strings?
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-03-21T15:57:37.663Z
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
CC BY-SA 3.0
2012-03-21T16:07:14.300Z
Does your construction work for 3CNF clauses with three distinct leterals?
Mohammad Al-Turkistany
<cc.complexity-theory>
Density of distinct satisfying assignments for uniquely satisfiable formulas
Mohammad Al-Turkistany
# Density of distinct satisfying assignments for uniquely satisfiable formulas

(Asked by: username_0 on 2012-03-21)

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.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: In your construction, how many variables do you need for n-bit strings?  
> **username_1**: 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.  
> **username_0**: Does your construction work for 3CNF clauses with three distinct leterals?  

---

## 1 answers

### Answer by username_2 on 2012-03-21. Score: 5

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


---

