<p>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$.)
<em>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$.</em></p>

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

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

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

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

<p>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 &lt; \delta &lt; 1$ for large enough $n$, with $\delta \to 1$ as $n \to \infty$.</p>

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

<p>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) &lt; r_n &lt; 1/(12n)$ for $n \ge 1$.)
Now $u/(1+u) &gt; 1/2$ for large enough $n$, so there are $2^{\Omega(n)}$ complete 1-SAT instances, and hence $2^{\Omega(n)}$ UniqueSAT instances.</p>

CC BY-SA 3.0
2015-07-27T14:47:59.497Z
2015-07-28T14:26:18.733Z
2015-07-28T14:26:18.733Z
András Salamon
<p>UniqueSAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. Unique SAT is CoNP-hard and $US$-complete.</p>

<blockquote>
  <p>What is the density of UniqueSAT?</p>
</blockquote>

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

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

<p><strong>Motivation:</strong> 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. <a href="http://www.cs.umd.edu/~jkatz/complexity/f05/lecture6.pdf" rel="nofollow">Mahaney's Theorem</a> gives evidence that Karp reduction can not exist between two $NP$ sets with densities separated by "large gap". </p>

CC BY-SA 3.0
2015-07-27T02:04:19.097Z
Aha, How about D= $2^{\Omega(n)}$?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-07-27T08:09:31.427Z
Doesn't a coNP-hard language being sparse imply P = NP?
Daniel Apon
CC BY-SA 3.0
2015-07-27T09:20:39.060Z
@DanielApon I know that NP-hard language being sparse imply P = NP (from a known result).
Mohammad Al-Turkistany
<cc.complexity-theory><unique-solution>
Evidence that UniqueSat is dense
Mohammad Al-Turkistany
# Evidence that UniqueSat is dense

(Asked by: username_0 on 2015-07-26)

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](http://www.cs.umd.edu/~jkatz/complexity/f05/lecture6.pdf) gives evidence that Karp reduction can not exist between two $NP$ sets with densities separated by "large gap".

**Tags:** cc.complexity-theory, unique-solution
> **Comments:**
> **username_0**: Aha, How about D= $2^{\Omega(n)}$?  
> **username_1**: Doesn't a coNP-hard language being sparse imply P = NP?  
> **username_0**: @DanielApon I know that NP-hard language being sparse imply P = NP (from a known result).  

---

## 1 answers

### Answer by username_2 on 2015-07-27. Score: 4 | Accepted answer

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.


---

