# Conditions for tractability of 3SAT-Satisfiability

What I'm wondering specifically is if there is an interesting condition on the percentage of assignments that satisfy a 3SAT formula to guarantee that such problems are tractable.

Suppose for example the class of 3SAT problems that $\epsilon(n) 2^n$ of the $2^n$ possible assignments satisfy the boolean formula; can we efficiently find a satisfying assignment? For what $\epsilon$ is the resulting problem in P?

Edit note: Replaced $\epsilon$ with $\epsilon(n)$ to clear up confusion.

• A simple observation: If $\epsilon$ is at most inverse polynomially small, then sampling uniformly $1/\epsilon$ times will yield a solution in expected polynomial time. So if $\epsilon$ is between 1 and 1/poly(n), this problem is easy (it's in ZPP). Nov 19 '10 at 5:46
• similarly, if 1/eps is quasipolynomial, then you have a randomized quasipoly time algorithm, which itself would be surprising Nov 19 '10 at 6:54

## 1 Answer

Yes. If $0< \epsilon <1$ is a constant (or $1/\textit{polylog}(n)$), and you are promised that at least $\epsilon 2^n$ of all possible assignments are satisfying the input 3CNFs, then you can find such an assignment in deterministic polynomial-time.

The algorithms is not difficult:

Claim: Under the promise stated, there must exist a constant size set $S$ of variables that hits all clauses in the 3CNF, in the sense that every 3-clause must contain a variable from $S$.

Proof of claim (sketch): Otherwise, there must exist a large enough family of 3-clauses from the 3CNF, in which each variable occurs only once. But this family, when sufficiently large, has already less than $\epsilon$ fraction of satisfying assignments. QED

Thus, you can run over all possible (constant number) of assignments to $S$. Under every fixed assignment to $S$, the 3CNF becomes a 2CNF, by the assumption that $S$ hits the original 3CNF. Now, you can use the known polytime deterministic algorithm for finding a satisfying assignment for 2CNF formulas. Overall, you get a polynomial time upper bound.

The algorithm for 2SAT is I think already in S. Cook famous 1971 paper.

The algorithm for 3CNFs is from: L. Trevisan A Note on Deterministic Approximate Counting for k-DNF In Proc. of APPROX-RANDOM, Springer-Verlag, page 417-426, 2004

The original paper showing the result for 3CNF is: E. Hirsch, A fast deterministic algorithm for formulas that have many satisfying assignments, Journal of the IGPL, 6(1):59-71, 1998

• Thanks for the answer. I was actually interested in non-constant $\epsilon$ but learning the existence of a deterministic algorithm is interesting. I edited the question to make it more clear. Nov 19 '10 at 8:21
• @Rafi, I think the same algorithm works for non-constant $\epsilon = 1/polylog(n)$. Nov 19 '10 at 9:13
• How do you construct S? Nov 19 '10 at 9:39
• @Radu, I think you can do that greedily: pick an arbitrary first clause $C_1$. Then pick another clause $C_2$ whose variables are disjoint from $C_1$. Keep doing this, until you can't find a clause with disjoint variables to the clauses you already picked. So the variables in the clauses you picked are the hitting set. Nov 19 '10 at 10:37