Sunday, March 11, 2007

When there are many satisfying assignments ...

My solution to Problem 4 in Problem Set 2 is an adaptation of Hirsch'98. This solution is somewhat dissimilar to Sipser-Saxe-Furst (contrary to what the hint in the Problem Set suggests) and so I wonder if someone has a different (easier) solution.

On the other hand, reading Hirsch's paper raised an interesting question. As a corollary of this exercise we know that formulas with bounded-width clauses and many satisfying assignments have short (constant size) partial satisfying assignments. It is an open question (according to Hirsch) whether a similar procedure exists for CNF formulas with unbounded-width clauses.

To suggest that maybe this is not possible, (in Remark 6 of Hirsch'98) Hirsch constructs a CNF for which more than half of all assignments are satisfactory and yet for every partial assignment on SQRT(n) variables there exists a corresponding complete assignment which is unsatisying.

Hirsch, however, fails to point out that the constructed CNF formula might (and most likely will) be exponential in size. This raises a new, more concrete, open question: Is there a way to modify the present algorithm such that it takes advantage of bounds on formula length in addition to clause-width that solves the problem for CNFs with unbounded-width clauses in sub-exponential time?


Petar Maymounkov said...

This promise problem can be solved wither using Hirsch or Furst-Saxe-Sipser. We now construct a general CNF formula (i.e. no bound on clause-width is assumed) such that (i) more than 1/2 of assignments are satisfying, (ii) the shortest partial satisfying assignment has length SQRT(n), (iii) the formula has size less than 3n, and (iv) both Hirsch and Furst-Saxe-Sipser algorithms fail to find a satisfying assignment in polynomial time.

The formula F is defined on 2n variables x1,...,xn and y1,...,yn.

All 2*SQRT(n) clauses are of size SQRT(n). The first SQRT(n) clauses are simply a partition of x1,...,xn.

The second batch of SQRT(n) clauses is obtained by starting from a partition of y1,...,yn and simply adding xi to the i-th such clause.

One can verify that the above claims hold.

Anonymous said...

nice read. I would love to follow you on twitter.