4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 21 '12 at 14:24
  • 1
    $\begingroup$ In your construction, how many variables do you need for n-bit strings? $\endgroup$ – Mohammad Al-Turkistany Mar 21 '12 at 15:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 21 '12 at 15:57
  • 1
    $\begingroup$ Does your construction work for 3CNF clauses with three distinct leterals? $\endgroup$ – Mohammad Al-Turkistany Mar 21 '12 at 16:07
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.