Asymptotic bounds on number of 3SAT formulas with unique solutions

Question

A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if there is a sparse NP-complete set (under Karp reduction).

I would like to find the density of uniquely satisfiable 3SAT formulas. Is it super-polynomially dense or exponentially dense? What is known about the asymptotic lower bound on the number of 3SAT formulas with unique solutions?

Answer 1

It is dense, just as one would expect.

The number of uniquely satisfiable 3SAT formulas with $n$ variables and $n$ clauses is at least $2^n$, since for every possible assignment to the $n$ variables there is at least one 3SAT formula $\phi$ for which that is the satisfying assignment, and there are $2^n$ such assignments. A 3SAT instance with $n$ variables and $n$ clauses can be represented as a string of length $\ell = 3n \lg n$. Therefore, the number of such formulas is exponential in $\ell$.