patternMinor
Asymptotic bounds on number of 3SAT formulas with unique solutions
Viewed 0 times
uniquenumberwithasymptotic3satformulassolutionsbounds
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#11408, answer score: 4
Revisions (0)
No revisions yet.