Christoph Berkholz

Date: Thursday, July 11, 2013
Speaker: Christoph Berkholz
Venue: IST Austria

One approach to attack NP-hard satisfiability problems such as 3-SAT or
the Constraint Satisfaction Problem (CSP) is to design algorithms that
run in polynomial time but do not always succeed. A prominent family of such algorithms are the k-consistency tests that try to detect local inconsistencies in unsatisfiable CSP instances. Applied to the 3-SAT problem (that can be seen as a special CSP), the k-consistency test is equivalent to the search for resolution refutations of bounded width.

The k-consistency test and the search for width-k resolution refutations can be implemented in time n^O(k), hence are in polynomial time for every fixed k. We show that this cannot be done faster: Deciding whether a given 3-CNF formula has a resolution refutation of width k requires time n^{ck} for an absolute constant c>0. This unconditional complexity lower bound is ultimately obtained from the deterministic time hierarchy theorem using a reduction via known pebble games. In addition, the problem is EXPTIME-complete if k is part of the input.

Posted in RiSE Seminar