tag:blogger.com,1999:blog-5930603650314594489.post5274556466320490161..comments2014-10-21T05:12:13.040-07:00Comments on MIT 6.841: When there are many satisfying assignments ...MIT 6.841 Bloghttp://www.blogger.com/profile/05060258433867607037noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-5930603650314594489.post-28096790758773763782010-02-15T20:22:26.902-08:002010-02-15T20:22:26.902-08:00nice read. I would love to follow you on twitter.nice read. I would love to follow you on twitter.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5930603650314594489.post-85691249600287984132007-03-14T13:03:00.000-07:002007-03-14T13:03:00.000-07:00This promise problem can be solved wither using Hi...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.<BR/><BR/>The formula F is defined on 2n variables x1,...,xn and y1,...,yn.<BR/><BR/>All 2*SQRT(n) clauses are of size SQRT(n). The first SQRT(n) clauses are simply a partition of x1,...,xn.<BR/><BR/>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.<BR/><BR/>One can verify that the above claims hold.Petar Maymounkovhttp://www.blogger.com/profile/08703852824477094824noreply@blogger.com