## Compilation of intractable problems and its application to
artificial intelligence

**Paolo Liberatore**

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.

FTP
download.