## Preprocessing of intractable problems

**Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and
Marco Schaerf**
*Technical Report, Dipartimento di Informatica e Sistemistica,
Università di Roma ''La Sapienza''*

Some computationally hard problems --e.g., deduction in logical
knowledge bases-- are such that part of an instance is known well
before the rest of it, and remains the same for several
subsequent instances of the problem. In these cases, it is
meaningful to preprocess off-line this known part so as to simplify
the remaining on-line problem. In this paper we investigate such
a technique in the context of intractable, i.e., NP-hard,
problems. Recent results in the literature show that not all
NP-hard problems behave in the same way: for some of them
preprocessing yields polynomial-time on-line simplified problems
(we call them compilable), while for other ones there is strong
evidence that this should not happen. Our primary goal is to
provide a sound methodology that can be used either to prove or
disprove that a problem is compilable. To this end, we define
new models of computation, complexity classes, and reductions.
We find complete problems for such classes, completeness meaning
they are ''the less likely to be compilable''. We also
investigate preprocessing that does not yield polynomial-time
on-line algorithms, but generically ''decreases'' complexity.
This leads us to define ''hierarchies of compilability'', that
are the analog of the polynomial hierarchy. A detailed
comparison of our framework to the related idea of
''parameterized tractability'' shows the differences between the
two approaches.

@techreport{cado-etal-97-d,
title = {Preprocessing of intractable problems},
year = {1997},
author = {Cadoli, Marco and Donini, Francesco M. and Liberatore,
Paolo and Schaerf, Marco},
institution = {Dipartimento di Informatica e Sistemistica,
Universit\'a di Roma ''La Sapienza''},
number = {DIS 24-97},
}

HTTP download.

FTP
download.