Skip to main content
fixed an error
Source Link

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}g(n)$$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..

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}g(n)$ where $g(n)$ is the number of different 3-SAT instances.

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

Source Link

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}g(n)$ where $g(n)$ is the number of different 3-SAT instances.