Overcoming Intractability in the Knowledge Compilation Map

There exist several structures to represent functions in computer science. When a function has to be queried, that is, when trying to retrieve information about it (for instance its number of solutions), some representations may be more convenient than others. Knowledge compilation is a domain of computer science that deals with modifying the representation of a given function. A compilation is a (potentially costly) preprocessing step that changes the way a function is represented so that it becomes easier to query. Queries over a class of representations are called "tractable" when they can be answered using efficient (polynomial-time) procedures. Several classes of representations that have been identified render useful queries tractable. These classes are called compilation languages and are compared in a framework called the "knowledge compilation map". A first criterion to compare two languages is to look at the difference in memory space needed to represent a same function in the languages. But languages are also compared in terms of efficiency for answering queries. Every query considered is labelled as either as "tractable" or "intractable (unless some complexity hypothesis turns out false)" for each language. Practical compilers have been developed for several compilation languages. The purpose of the project is to study methods for answering queries labelled as "intractable" in these languages. We wish to show that compilation can reduce the complexity of answering a query even when it does not make it tractable. A first direction is to develop "parameterized" approaches to answer queries. On the one hand, we want to find procedures that are efficient when specific parameters of the structure representing the function are small. On the other hand, some intractable queries have parameters of their own, over which we can put restrictions to find special tractable cases. So for a given language and a family of queries, parameterization may yield efficient methods to answer all queries over a non-negligible subset of the language, or it may yield efficient methods to answer almost all queries over the whole language. Another direction is to study approaches to answer queries approximately. Given a family of queries and a language, we will look for efficient methods answering almost all queries of the family correctly and, when applicable, we will look for efficient methods that return answers close to the real ones. So far, approximation has been used during the compilation step. The idea was to decrease the size of the compiled representation in exchange for introducing errors in the function represented. Rather than compiling an approximation of the function in a language followed by exact query-answering, we propose compiling exactly into another language where smaller representations exist, and do approximate query-answering from there.