Limits of Preprocessing

Authors

  • Stefan Szeider Vienna University of Technology

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.

Downloads

Published

2011-08-04

How to Cite

Szeider, S. (2011). Limits of Preprocessing. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 93-98. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7816

Issue

Section

Constraints, Satisfiability, and Search