3
$\begingroup$

Assume that we are given a formula in 3-CNF such that at least 1% of the complete assignments satisfy it.

My question is how to find a satisfying assignment in polynomial time without the use of randomness? Prove the correctness and the upper bound on the running time for the algorithm that you suggest.

$\endgroup$
4

2 Answers 2

2
+100
$\begingroup$

For refresher, let's first remember (Wikipedia) that we can convert any Boolean expression into conjunctive normal form, which is defined as conjunction ("AND" $\land$) of one or more disjunctions ("OR" $\lor$) of one or more literals, and governed by six context-free grammar rules. Naively this is exponential in length, but we can efficiently reduce this to linear length by preserving satisfiability instead of equivalence (Wikipedia).

In this answer, we want to elaborate the answer from 2010 on the CS Theory site.

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

We interpret $n$ as $k$ since it is standard, 3CNFs as k-CNFs since it is relevant to the time complexity as the number of literals increases, $1/polylog(k)$ as $1/k$ since it is actually $1/polylog(2^k) = 1/k$. In our case $\epsilon = 0.01 = 1\%$ and $k = 3$, we are promised that at least $0.01 \times2^k$ of all possible assignments are satisfying the CNF, and we want to prove we can find such an assignment in deterministic polytime.

The algorithms is not difficult:

The noun is meant to be singular instead of plural.

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

The set $S$ contains the literals that hit all disjunctive clauses (first sentence of the refresher) in the CNF. For example, $S = \{B, \neg C\}$ means $B = true$ and $C = false$, hitting $(A \lor B \lor C)$, $(A \lor B \lor \neg C)$, $(A \lor \neg B \lor \neg C)$, $(\neg A \lor B \lor C)$, $(\neg A \lor B \lor \neg C)$, and $(\neg A \lor \neg B \lor \neg C)$, but not hitting $(A \lor \neg B \lor C)$ and $(\neg A \lor \neg B \lor C)$. The claim here is that the smallest size of $S$ is constant (only inversely proportional to $\epsilon$) instead of non-constant (proportional to $k$).

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

This is a proof by contradiction. We know the size of $S$ is at least constant and at most linear, since there are only $k$ literals. We know the number of clauses in the CNF is linear (last sentence of the refresher). If the smallest size of $S$ is nonconstant, its fixed assignments will only hit the clauses in the CNF a sublinear number of times statistically (side note: constant smallest size -> linear number of times), but this means the number of satisfying assignments is also sublinear, contradicting the promise that it is linear. Therefore, the smallest size of $S$ is constant.

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.

We can reduce 3CNF to 2CNF according to the laws of Boolean algebra (Wikipedia) after choosing a fixed assignment from $S$. We observe that "false or" can be reduced through removal, as well as "true and". We also observe that "true or" is immediately true, and "false and" is immediately false. The polytime algorithm for 2CNF is linear (Wikipedia).

Here's a distributive law example $A \lor (B \land C)$, we will work with its CNF form.

We know $S = \{A\}$ works, as well as $S = \{B, C\}$. Let's choose a fixed assignment $B$ from $S = \{B, C\}$ and reduce the 3CNF.

$(A \lor B) \land (A \lor C) = (A \lor true) \land (A \lor C) = (A) \land (A \lor C)$

Here's an XOR example $A \oplus B \oplus C$, we will work with its CNF form.

We know $S = \{A, \neg B, \neg C\}$, $S = \{A, B, C\}$, and some others work. Let's choose a fixed assignment $A$ from $S = \{A, \neg B, \neg C\}$ and reduce the 3CNF.

$(A \lor B \lor C) \land (A \lor \neg B \lor \neg C) \land (\neg A \lor \neg B \lor C) \land (\neg A \lor B \lor \neg C)$

$= (true \lor B \lor C) \land (true \lor \neg B \lor \neg C) \land (false \lor \neg B \lor C) \land (false \lor B \lor \neg C)$

$ = true \land true \land (\neg B \lor C) \land (B \lor \neg C)$

$ = (\neg B \lor C) \land (B \lor \neg C)$

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

Read the above references and other references as may be necessary.

$\endgroup$
8
  • $\begingroup$ @S.M. the contradiction is complete though. it's in the form: assume a, infer b from a -> b, infer ~b from contradiction, infer ~a from modus tollens on a -> b. typically, people don't write the modus tollens as it is obvious, and a contradiction anywhere is a contradiction everywhere. $\endgroup$ Commented Feb 24 at 19:01
  • $\begingroup$ @S.M. You are correct on "Because S isn't linear, it's non-constant." I've edited the answer to reflect this. $\endgroup$ Commented Feb 25 at 12:11
  • $\begingroup$ @S.M. I literally did though, just with words. "We assume the smallest size of S is non-constant" means assume |S| > f, where f is constant function. I then showed that its conclusion leads to contradiction, so |S| > f can't be true. If you want to directly show that |S| < f, instead of using contradiction, then I don't know how to do it, and I doubt it is possible since it is not obvious. If you find a way, that would be a candidate for your own separate answer. $\endgroup$ Commented Feb 25 at 12:34
  • $\begingroup$ @S.M. I don't think it's helpful, I don't really understand, but as far as I can guess, the comment only conclude this sentence "We know the number of clauses in the CNF is linear (read the refresher)." In my honest opinion, it would be easiest to just understand my answer. I don't think it can get any easier, I proofread it so many times and can't see anything wrong with it anymore. $\endgroup$ Commented Feb 25 at 16:20
  • $\begingroup$ Okay, just say what does meaning of 3-clauses from 3cnf? What does meaning of "3-clauses" $\endgroup$
    – S. M.
    Commented Feb 25 at 18:13
2
$\begingroup$

As mentioned by Clement C. on CS Theory, this is answered at Conditions for tractability of 3SAT-Satisfiability. You can even replace 1% with any other positive constant.

$\endgroup$
3
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Promise_problem. I didn't provide that answer. It's not my answer. I'm just linking to it. $\endgroup$
    – D.W.
    Commented Jan 24 at 20:48
  • $\begingroup$ I believe this answer should be expanded further to qualify for the bounty, since an answer is more than a comment. It could quote the claim and proof sketch, or other things. It could explain plugging in this special case from the general case. It will be more useful and searchable for future readers. $\endgroup$ Commented Jan 28 at 8:54
  • 1
    $\begingroup$ @KennethKho, makes sense! If you have any interest in writing an answer, go for it! This is all that I plan to write at this time. $\endgroup$
    – D.W.
    Commented Jan 28 at 18:27

Your Answer

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

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