Compilation of Intractable Problems and Its Application to Artificial Intelligence
Paolo Liberatore · 2004
Intractable problems are hard to solve. Since the work "has to be done", various solutions have been developed. The two classical ones are the language restriction and the approximation. The first solution is to admit input strings only if they have a certain form. The second one is to find a solution that can be sometimes incorrect. In this dissertation we concentrate on compilation. The basic scenario is the following one: we have an intractable problem, thus a problem for which it is believed no polynomial algorithm exists. However, each instance of this problem 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 compil...