## Preprocessing of intractable problems

**Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and
Marco Schaerf**
*Information and Computation*

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
useful 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 their compilability imply some
consequences that are considered unlikely. Our primary goal is
to provide a sound methodology that can be used to either 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 idea of ''parameterized
tractability'' shows the differences between the two approaches.

@article{cado-etal-02-c,
title = {Preprocessing of intractable problems},
year = {2002},
author = {Cadoli, Marco and Donini, Francesco M. and Liberatore,
Paolo and Schaerf, Marco},
journal = {Information and Computation},
pages = {89--120},
number = {2},
volume = {176},
}

HTTP download.

FTP
download.

doi: 10.1006/inco.2001.3043