Limits of Preprocessing

Many important computational problems that arise in various areas of AI are intractable. Nevertheless, AI research was very successful in developing and implementing heuristic solvers that work well on realworld instances. An important component of virtually every solver is a powerful polynomial-time preprocessing procedure that reduces the problem input. For instance, preprocessing techniques for the propositional satisfiability problem are based on Boolean Constraint Propagation (see, e.g., Eén and Biere, 2005), CSP solvers make use of various local consistency algorithms that filter the domains of variables (see, e.g., Bessière, 2006); similar preprocessing methods are used by solvers for Nonmonotonic and Bayesian reasoning problems (see, e.g., Gebser et al., 2008, Bolt and van der Gaag, 2006, respectively). Until recently, no provable performance guarantees for polynomial-time preprocessing methods have been obtained, and so preprocessing was only subject of empirical studies. A possible reason for the lack of theoretical results is a certain inadequacy of the P vs NP framework for such an analysis: if we could reduce in polynomial time an instance of an NPhard problem just by one bit, then we can solve the entire problem in polynomial time by repeating the reduction step a polynomial number of times, and P NP follows. With the advent of parameterized complexity (Downey, Fellows, and Stege, 1999), a new theoretical framework became available that provides suitable tools to analyze the power of preprocessing. Parameterized complexity considers a problem in a two-dimensional setting, where in addition to the input size n, a problem parameter k is taken into consideration.