World's most popular travel blog for travel bloggers.

# [Solved]: Asymptotic bounds on number of 3SAT formulas with unique solutions

, ,
Problem Detail:

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?

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