Limits of Preprocessing

Details Limits of Preprocessing Limits of Preprocessing

2011-04-29

arxiv.org/abs/1104.5566v2

Computer Science

Artificial Intelligence

This is a slightly longer version of a paper that appeared in the proceedings of AAAI 2011

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Limits of Preprocessing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Limits of Preprocessing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Limits of Preprocessing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-17284