# Preprocessing of intractable problems

Information and Computation, Volume 176, Number 1, page 89--120 - aug 2002

Download the publication :

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.

**BibTex references**

@Article{CDLS02,

author = {Marco Cadoli and Francesco M. Donini and Paolo Liberatore and Marco Schaerf},

title = "Preprocessing of intractable problems",

journal = "Information and Computation",

number = "1",

volume = "176",

pages = "89--120",

month = "aug",

year = "2002",

url = "http://www-ictserv.poliba.it/publications/2002/CDL

S02"

}

## Other publications in the database