English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a first theoretical analysis of the power of polynomial-timepreprocessing for important combinatorial problems from various areas in AI. Weconsider problems from Constraint Satisfaction, Global Constraints,Satisfiability, Nonmonotonic and Bayesian Reasoning under structuralrestrictions. All these problems involve two tasks: (i) identifying thestructure in the input as required by the restriction, and (ii) using theidentified structure to solve the reasoning task efficiently. We show that formost of the considered problems, task (i) admits a polynomial-timepreprocessing to a problem kernel whose size is polynomial in a structuralproblem parameter of the input, in contrast to task (ii) which does not admitsuch a reduction to a problem kernel of polynomial size, subject to acomplexity theoretic assumption. As a notable exception we show that theconsistency problem for the AtMost-NValue constraint admits a polynomial kernelconsisting of a quadratic number of variables and domain values. Our resultsprovide a firm worst-case guarantees and theoretical boundaries for theperformance of polynomial-time preprocessing algorithms for the consideredproblems.

Guarantees and Limits of Preprocessing in Constraint Satisfaction and Reasoning