Knowledge compilation offers a compelling approach to coping with computationally hard problems. This line of research was initiated in the early 1990s, and since then has become a very active and progressing field. Knowledge compilation proceeds in two phases: In the first phase the input data is compiled into a new representation, which is then used in a second phase to execute a number of individual tasks efficiently. Ideally, one aims at a compilation that causes only a polynomial increase in space, and the classical theory of compilation offers theoretical tools to decide whether such a compilation is possible or not. However, systematic research shows that most relevant problems are not compilable with a polynomial increase in space. Hence, the classical theory cannot provide reasonable guarantees for these problems.
The goal of this project is to overcome this limit of classical knowledge compilation by utilizing structural aspects of problem inputs (such as as tree-likeness, degree of cyclicity, or backdoor size). As the key to this goal we propose to study knowledge compilation within the framework of parameterized complexity, which has become an important and successful research direction in algorithms and complexity. Parameterized complexity provides powerful methods and tools for exploiting structural aspects of problems and is therefore ideally suited for this purpose. Using parameters we can exploit structural aspects of the input in order to support the compilation. Hence we expect positive results in terms of upper bounds for compilation space and compilation time for problems that are not compilable in the classical sense.
The proposed research will be driven by the study of concrete compilation problems that arise within broad areas like knowledge representation, abductive reasoning, logic programming, abstract argumentation, and propositional planning. Based on the insights gained from working on these concrete problems we will develop a rigorous approach to knowledge compilation that extends and refines the classical theory, and provides theoretical tools for parameterized upper and lower bounds. The theoretical objectives will be complemented by an empirical investigation on how parameters are distributed in real-world problem instances.
