Evidence that UniqueSat is dense

Question

UniqueSAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. Unique SAT is CoNP-hard and $US$-complete.

What is the density of UniqueSAT?

I know only weak evidence to support that it can not be sparse: All known CoNP-complete sets are dense and UniqueSAT is CoNP-hard.

Here, density $D$ of a set $S$ refers to the number of strings of length less than $n$ in the language. A set $S$ is exponentially dense if its density is $D=\Omega(2^{n^\epsilon})$ for some $\epsilon \gt 0$ and for infinitely many $n$ and sparse if $D$= $O(poly(n))$.

Motivation: I would like to link the existence of Karp reduction from SAT to UniqueSAT to the existence of "large gap" between the density of the two problems. Mahaney's Theorem gives evidence that Karp reduction can not exist between two $NP$ sets with densities separated by "large gap".

Answer 1

As far as I can tell, UniqueSAT is exponentially dense, in the sense that it contains $2^{\Omega(n)}$ instances of size $n$. (This is a stronger requirement than $2^{n^\varepsilon}$ for infinitely many $n$.) The following argument works even for the revised definition of "dense" introduced in version 5 of the question, where all instances of size up to $n$ are taken into account. Note that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$.

Consider formulas in CNF with $v$ clauses, each clause containing exactly one literal, such that each variable occurs precisely once in the formula. An example of such a "complete 1-SAT" formula for $v=3$ is $x_1\land x_2 \land \lnot x_3$, completely specifying the solution $x_1 = 1, x_2 = 1, x_3 = 0$.

We establish an exponential lower bound for the number of complete 1-SAT formulas of size $n$. Logarithms are base 2.

Complete 1-SAT formulas each have precisely one solution, and with $v$ variables such a formula has size $v(1+\log v)$. There are also $2^v.v!$ distinct complete 1-SAT formulas over $v$ variables.

We then just need to ensure that $v$ is as large as possible in terms of the instance size $n$.

Let $v = n/(\log n)^\delta$ for some $\delta = \delta(n)$. For the size of complete 1-SAT formulas with $v$ variables to be precisely $n$ bits, we require that $n = v(1+\log v) = (n/(\log n)^\delta)(1+\log n - \delta\log\log n)$ so $1+\log n - \delta\log\log n = (\log n)^\delta$. We can always choose $\delta$ appropriately to satisfy this expression; note that $1/2 < \delta < 1$ for large enough $n$, with $\delta \to 1$ as $n \to \infty$.

This already shows that there are at least $2^{n/\log n}$ such instances, so UniqueSAT is not sparse.

Moreover, the high order term of the exponent of $2^v.v!$ is then $n[(u/(1+u))-(\log e - 1)]$, where $u = \log n - \delta \log\log n$ and $\log e - 1 \approx 0.4427$. (For instance, this follows from Robbins' bounds for the factorial function, $\log n! = n\log n - n\log e + 0.5\log n +r_n\log e + 0.5(1+\log \pi)$, where $1/(12n+1) < r_n < 1/(12n)$ for $n \ge 1$.) Now $u/(1+u) > 1/2$ for large enough $n$, so there are $2^{\Omega(n)}$ complete 1-SAT instances, and hence $2^{\Omega(n)}$ UniqueSAT instances.