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

$\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$ Nov 19 '10 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$ Nov 19 '10 at 6:54
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

$\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$ Nov 19 '10 at 8:21
  • 1
    $\begingroup$ @Rafi, I think the same algorithm works for non-constant $ \epsilon = 1/polylog(n) $. $\endgroup$ Nov 19 '10 at 9:13
  • $\begingroup$ How do you construct S? $\endgroup$ Nov 19 '10 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$ Nov 19 '10 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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