11
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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). $\endgroup$
    – Robin Kothari
    Nov 19, 2010 at 5:46
  • 1
    $\begingroup$ similarly, if 1/eps is quasipolynomial, then you have a randomized quasipoly time algorithm, which itself would be surprising $\endgroup$
    – Suresh Venkat
    Nov 19, 2010 at 6:54

1 Answer 1

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Rafi Witten
    Nov 19, 2010 at 8:21
  • 1
    $\begingroup$ @Rafi, I think the same algorithm works for non-constant $ \epsilon = 1/polylog(n) $. $\endgroup$
    – Iddo Tzameret
    Nov 19, 2010 at 9:13
  • $\begingroup$ How do you construct S? $\endgroup$
    – Radu GRIGore
    Nov 19, 2010 at 9:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – Iddo Tzameret
    Nov 19, 2010 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.