Search code examples
algorithmboolean-operationssat

Design a branching algorithm breaking the triviality barrier for 3-SAT problem

I am working on an example that says: For 3-SAT problem we have clause c=l1 or l2 or l3. How many satisfying assignments are possible. Considering these assignments, design a branching algorithm breaking the triviality barrier.

I am new to this and my question is not on the solution, but on the interpretation of the question:

  1. In my understanding there are 2^3=8 possible solutions, 7 of each are satisfying. Does the question ask to find these assignments or to find number of possible solutions, because there will be always 7 possible solutions for such clause.

  2. What does it mean to break the triviality barrier, does it mean not to use brute force to find all possible assignments and count correct?

  3. Any directions or better interpretation would be welcome.

Solution

    1. The “trivial” algorithm here branches on each variable recursively and then evaluates the formula. The observation here is that, by branching on at most three variables at a time and discarding the obviously infeasible assignment, we end up branching 7 ways for each three variables instead of 8.

    2. I’d say breaching triviality means finding an algorithm that’s O(2^(delta n)) for some delta < 1. Using the hint you should be able to get an O(7^(n/3) poly(n))-time algorithm, which qualifies.