2014/06/12 by Serge Gaspers, Stefan Szeider, Gaspers, Serge +1
Computer Science · #AI-based Problem Solving and Planning #Constraint Satisfaction and Optimization #Logic, Reasoning, and Knowledge #cs.AI #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1406.3124
arXiv admin note: substantial text overlap with arXiv:1104.2541, arXiv:1104.5566
arxiv created 2014/06/12 · arxiv updated 2014/06/13
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 under structural restrictions. All these problems involve two tasks: (i) identifying the structure in the input as required by the restriction, and (ii) using the identified structure to solve the reasoning task efficiently. We show that for most of the considered problems, task (i) admits a polynomial-time preprocessing to a problem kernel whose size is polynomial in a structural problem parameter of the input, in contrast to task (ii) which does not admit such a reduction to a problem kernel of polynomial size, subject to a complexity theoretic assumption. As a notable exception we show that the consistency problem for the AtMost-NValue constraint admits a polynomial kernel consisting of a quadratic number of variables and domain values. Our results provide a firm worst-case guarantees and theoretical boundaries for the performance of polynomial-time preprocessing algorithms for the considered problems.