Intractable problems are hard to solve. Since the work "has to be done", various solutions have been developed. In this dissertation we concentrate on compilation. We have an intractable problem, such that each instance is composed of two parts, one (called the fixed part) is known in advance, while the other (called the varying part) only comes at execution time. Our idea is to solve the problem in two steps: 1. Take the fixed part and compile it into a new data structure; 2. Take the new data structure and the varying part, and produce the output. If the second step can be accomplished in polynomial time, the problem is said to be compilable to polynomial time. The dissertation contains a formal definition of compilation and compilabil- ity of hard problems. Namely, two hierarchies of classes of problems (similar to the polynomial hierarchy) are defined. One of them is used to prove that problems are compilable, while the other one is mainly used to prove that some problems are not compilable. Applications of this framework includes: compilability of AI problems, problems on graphs, compact representation of AI operators. A comparison with the non-uniform polynomial hierarchy and with the FPT classes are given.
@phdthesis{libe-98-c,
title = {Compilation of intractable problems and its application to artificial
intelligence},
year = {1998},
author = {Liberatore, Paolo},
school = {Dipartimento di Informatica e Sistemistica, Universit\`a di Roma "La
Sapienza"},
}
HTTP download.