Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI

At the core of several key areas of AI and reasoning are hard-to-solve computational problems, such as the processing of constraints, the execution of reasoning tasks, and the verification of the soundness of procedures and protocols. All these problems are in general intractable and pose a challenge to algorithm design, specifically as today's ICT applications demand for larger and larger instances to be solved. This requires new and more powerful algorithms, in order to facilitate a further progress in the technological innovation. Fortunately, typical problem instances tend to contain some form of HIDDEN STRUCTURE, as the instances are the product of certain processes. This research project is about revealing this hidden structure and utilizing it for an efficient solution. More specifically, we will capture hidden structure in terms of the powerful new concept of BACKDOOR TREEWIDTH which combines orthogonal approaches in a nontrivial way. The project aims at: 1) the in-depth study of foundations and applications of backdoor treewidth 2) the refinement of algorithms towards effective implementations 3) its instantiation in core areas: a) Valued CSP, a meta-problem entailing prominent optimization problems b) QBF-SAT, the canonical PSPACE complete problem with applications in verification c) Abstract Argumentation, the canonical problem to resolve conflicts between arguments d) Answer-Set Programming, a key meta-problem in knowledge representation and reasoning