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.

The main objective of the project was to investigate hard intractable problems and to find situations where the hardness can be overcome. Our main contribution is the discovery of efficient algorithms for solving hard quantitative problems in an approximate yet rigorous way. We considered counting problems where one is asked to count various objects, or solutions, over a specific data structure. We have looked are hard problems, in the sense that there may be many solutions to count and probably no resolution method doing significantly better than a costly bruteforce enumeration of all possible solutions. We studied several such counting problems over a fundamental data structures (for instance, non-deterministic automata or context-free grammars) and we have shown that, while these problems are difficult for *exact* counting, there are in fact easy for *approximate* counting. Our main achievement is the creation of efficient polynomial-time algorithms to return an estimate of the true number of solutions with rigorous guarantees on the quality of the estimate: the ratio between the approximate count and the true count is controlled and can be made as close to 1 as desired and the probability of failure can be made vanishingly small.