<p>Yes. If $ 0&lt; \epsilon &lt;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 <em>deterministic</em> polynomial-time.</p>

<p>The algorithms is not difficult: </p>

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

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

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

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

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

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

CC BY-SA 2.5
2010-11-19T08:21:54.457Z
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.
Rafi Witten
CC BY-SA 2.5
2010-11-19T09:13:14.767Z
@Rafi, I think the same algorithm works for non-constant $ \epsilon = 1/polylog(n) $.
Iddo Tzameret
CC BY-SA 2.5
2010-11-19T09:39:08.413Z
How do you construct S?
Radu GRIGore
CC BY-SA 2.5
2010-11-19T10:37:50.077Z
@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.
Iddo Tzameret
CC BY-SA 2.5
2010-11-19T07:53:45.913Z
2010-11-19T09:36:19.280Z
2010-11-19T09:36:19.280Z
Iddo Tzameret
<p>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.</p>

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

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

CC BY-SA 2.5
2010-11-19T05:46:02.750Z
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).
Robin Kothari
CC BY-SA 2.5
2010-11-19T06:54:24.863Z
similarly, if 1/eps is quasipolynomial, then you have a randomized quasipoly time algorithm, which itself would be surprising
Suresh Venkat
CC BY-SA 4.0
2024-02-24T20:21:10.993Z
@RobinKothari in below answer in proof section, I don't understand this sentence "when sufficiently large, has already less than ϵ
 fraction of satisfying assignments". Would tell me how to prove the correctness of this sentence.
S. M.
<cc.complexity-theory><ds.algorithms><sat><np>
Conditions for tractability of 3SAT-Satisfiability
Rafi Witten
# Conditions for tractability of 3SAT-Satisfiability

(Asked by: username_0 on 2010-11-19)

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.

**Tags:** cc.complexity-theory, ds.algorithms, sat, np
> **Comments:**
> **username_1**: 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).  
> **username_2**: similarly, if 1/eps is quasipolynomial, then you have a randomized quasipoly time algorithm, which itself would be surprising  
> **username_3**: @RobinKothari in below answer in proof section, I don't understand this sentence "when sufficiently large, has already less than ϵ  fraction of satisfying assignments". Would tell me how to prove the correctness of this sentence.  

---

## 1 answers

### Answer by username_4 on 2010-11-19. Score: 12

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

> **Comments:**
> **username_0**: 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.  
> **username_4**: @Rafi, I think the same algorithm works for non-constant $ \epsilon = 1/polylog(n) $.  
> **username_5**: How do you construct S?  
> **username_4**: @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.  

---

