Limits of PreprocessingProceedings of the Twenty-Fifth Conference on Artificial Intelligence, (AAAI 2011), pp. 93-98, AAAI Press, Menlo Park, California, 2011. Abstract:We present a first theoretical analysis of the power of polynomial-time preprocessing for important combinatorial problems from various areas in AI. We consider problems from Constraint Satisfaction, Global Constraints, Satisfiability, Nonmonotonic and Bayesian Reasoning. We show that, subject to a complexity theoretic assumption, none of the considered problems can be reduced by polynomial-time preprocessing to a problem kernel whose size is polynomial in a structural problem parameter of the input, such as induced width or backdoor size. Our results provide a firm theoretical boundary for the performance of polynomial-time preprocessing algorithms for the considered problems.Preprint available from [arXiv:1104.5566v2] |